# Question
Title: Undecidable Problem for Regular Languages
It might seems weird, but, Are there any **undecidable** problems concerning regular languages? I mean questions concerning the regular languages, not the problems like "Is the language of a TM regular?".

Clarification: By the questions regarding regular languages, I mean that the problem consists of regular languages, i.e. the relation between two or more regular languages, and/or about the properties of a regular language.

Thanks in advance

# Answer
Yes, there are undecidable problems like the Post Correspondence Problem that can be coded into the language of a finite state automaton, as explained in my earlier answer to a (slightly broader) question: https://cs.stackexchange.com/a/6198

The result can be traced to a paper by Engelfriet and Rozenberg dealing with the so called twin shuffle operation. *Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages* (J. ACM) doi:10.1145/322203.322211

Recently Endrullis, Shallit and Smith presented the paper *Undecidability and Finite Automata* at the conference DLT2017 (doi:10.1007/978-3-319-62809-7\_11, arxiv:1702.01394) which deals with your question:

> **Abstract.** Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove three related problems are decidable. We apply one result to prove the undecidability of a related problem about k-automatic sets of rational numbers.

I am very proud that one of the references in this paper is to my earlier SE answer!
> 9 votes

# Answer
This answer might not be entirely to your taste because it uses Turing machines. I think it's a valid answer, since the input to the problem is a regular language, rather than a Turing machine.

Fix a universal Turing machine $U$ and consider the problem "Does $U(x)$ halt for every $x\in L$?" (or for some $x\in L$). For concreteness, we can represent $L$ itself by giving an encoding of a DFA that decides it.

It's easy to see that this language is undecidable: we can reduce the halting problem to it by translating the question "Does $M(w)$ halt?" into "Does $U(x)$ halt for every $x\in L$?", where $L = \\{\langle M;w\rangle\\}$. It's easy to translate a description of $M$ and $w$ into a description of a DFA that accepts only the string $\langle M;w\rangle$.
> 2 votes

---
Tags: computability, regular-languages, undecidability
---


# Question
Title: Find minimum time path between two nodes
I am trying to write an algorithm for finding best path for an electric vehicle to navigate through network of chargers.

* A graph with Vertices representing charges and Edges representing distances among them is provided
* Assume that car drives at constant speed (ex. 80 mph) and has a fixed maximum mile Range when its fully charged (ex. 300 miles)
* Each charger has a rate associated with it given in miles/minute (how many miles are added for a minute of charging)
* Goal is to go from charger A to charger B in minimum amount of time. Assume car is fully charged when you start.
* You can stop at multiple chargers on the way and charge the car. You don't have to fully-charge the car at all chargers. You can decide how much time to spend at these chargers
* At any point of time remaining range of the car must stay above 0

**Output**

* Find minimum time path between A and B
* List of chargers you will visit starting from A and ending at B.
* Time spent charging at each of these chargers
* Total travel time in minutes

I tried a solution using Dijsktra's shortest path algorithm, but does not fully solve the problem. I don't need help with coding. I don't need help with coding. I want some insights on how to design the algorithm.

# Answer
> 1 votes
This can be done in polynomial time.

I'm assuming:

* All our your nodes are charging stations. If not, you can create a new graph that consists of only charging-stations (including start/finish) by finding the all-pairs shortest paths *(or just running Dijkstra's multiple times)*
* The time spent charging is proportional to the distance driven. If there are eg. paths that are shorter but require larger charges, the problem becomes much more difficult.

The optimal method will be to drive as far as you can on one charge, then fill up your battery only barely enough to make it to the next charging station. You can do this by adding weight to each edge $\overline{AB}$ equal to the time needed to wait at $A$ while charging, taking into account the battery's initial charge.

We'll do this by altering Djikstra's algorithm. We need to make two changes to the algorithm

1. In addition to giving each node a **TentativeDistance**, also assign it a **CurrentBatteryLevel**. This will be the battery level when reaching the node, *before* doing any charging. Set it to full for the initial node.
2. When expanding the current node and calculating the tentative distance to a neighbor-node, add to the edge-weight the amount of time that will need to be spent charging. If there is enough charge to make it there, this will be 0, and the potential **CurrentBatteryLevel** for the neighbor-node will be \>= 0. If there is not, it will be the time required to charge the battery enough so that, when you make it there, **CurrentBatteryLevel** will be 0.

This works because we're still guaranteed to have found the shortest path to a node when expanding it. This is true because there are no longer paths with shorter charging times, and we're only altering outgoing edges when expanding nodes (never incoming edges), so the assumptions of Dijkstra's algorithm still hold.

Also, since we only increase edge-weights, never decrease, if you have a heuristic you can still use A\*. It must consistent, since our algorithm breaks if we need to expand nodes multiple times.

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


# Question
Title: Can loops like this one be algorithmically transformed into multiplication
Are there known techniques for converting a loop like the following to an `if` and a multiplication?

```
while (x < 0) {
    x += 60;
}

```

It seems clear that this could be replaced with something like the following

```
if (x < 0) {
    x += f(x, 60);
}

```

where `f` contains no loops, presumably using multiplication. This would have the benefit of being faster for sufficiently large negative numbers.

Is there a well understood algorithm for finding `f` for an arbitrary loop of this form?

# Answer
> 4 votes
The name for this optimization seems to be **induction variable elimination**, there are some nice slides explaining the idea here.

# Answer
> 0 votes
What you want to do here is find a number, which when multiplied by 60 and added to x, will bring x above (or equal to) your chosen limit.

This number can be found by dividing the difference between x and 0 by 60, and taking the ceiling of the resulting value. The general function would be:

```
f(x,y) = ceil((limit-x) / y) * y

```

Note that when your limit is 0 the expression simplifies to:

```
f(x,y) = ceil(-x / y) * y

```

# Answer
> 0 votes
Here's how I went about it-
We know the loop keeps adding 60, (let the general case be known as k) till the input becomes positive.
Let input be x, we observe that when x lies between -59 and 0, we add 60 once, i.e when x-1 lies between -60 and -1 we add 60 once.
We can say from the observation that when x belongs to `[n*k,(n-1)*k)` we multiply k by n.
`f(x,k)= n*k if x belongs to [n*k,(n-1))`
From the above we can easily get the function `f(x,k)=ceil(|x-1|/k)*k`.
These steps are mere implementation of the principles which Cody posted above.

# Answer
> 0 votes
Simple

```
if(x < 0) {
    x = 60 - ((-x) % 60);
}

```

---
Tags: formal-languages, optimization, programming-languages, program-optimization
---


title: Why does the time/space tradeoff exist

text:
# Question
Title: Why does the time/space tradeoff exist
I'd like to know why when choosing how to optimize an algorithm that there almost always (always?) exists a time/space tradeoff.

Definition: https://simple.wikipedia.org/wiki/Space-time\_tradeoff.

My favorite example is a karnaugh map for simplifying boolean logic. It abstracts boolean logic away with just clever geometry:

Is there some sort of law from some mathematical theory to explain why this exists? Intuitively it seems to make sense, but the math would be nice.

Is this some property of information/computation? Is it guaranteed for any computation that can be performed? What about computations theoretically possible with infinite time, is a reciprocal guaranteed to exist that instead uses infinite space (or a middle ground that makes the time axis not go to infinity anymore)?

# Answer
## It doesn't. You're biased to results you find interesting.

If we measure a particular algorithm's space $s$ and time $t$ complexity, and then improve the algorithm. One of the following things can **and does** happen:

1. We reduce $s$ and leave $t$ unchanged.
2. We reduce $t$ and leave $s$ unchanged.
3. We reduce both $s$ and $t$.
4. We reduce $s$ and $t$ increases. **WOW!**
5. We reduce $t$ and $s$ increases. **WOW!**

Now 1, 2 and 3 happen all the time. Why are you not asking for a "mathematical principle" for them?

Because they are *boring*. Since we strictly improved the algorithm it must mean the previous algorithm was suboptimal, and is immediately forgotten. Only in cases 4 and 5 we suddenly have two algorithms which do not have a clear winner, and only then do you start comparing them and wondering about a "mathematical principle" behind this difference.

---

What's happening is that given two objectives, you get a plot of possible solutions:

Anything above and to the right of the critical red line is immediately forgotten as non-interesting, as there are algorithms that are strictly better in both $s$ and $t$. Your mind only looks at the red line (also known as the Pareto frontier), ignoring the rest of the plot.
> 5 votes

---
Tags: computability, optimization, information-theory
---


# Question
Title: Do exponents have higher time complexity than factorials?
My professor said exponentials will always have higher time complexity compared to polynomials. My question is, do exponentials also have higher time complexity than factorials?

I plotted a chart in Matlab to check it myself.

When range of x is small, from 1 to 10, I get the following chart,

```
%Matlab script
x  = [1 : 10];
y1 = factorial(x);
y2 = exp(x);

plot(x', [y1',y2']);
title("N! vs e^N");
legend("O(n!)", "O(e^n)");

```

Here factorial is clearly beating exponential.

But when I bump the range of x from 1 to 1000, I get the following chart,

```
x  = [1 : 1000];

```

Here exponential is clearly beating factorial.

So, can I say conclusively that exponentials will always have higher time complexity than both factorials and polynomials?

-

# Answer
> 3 votes
In fact $e^n$ is $o(n!)$. We could show it using the Stirling approximation by taking limit $$\lim\_{n\rightarrow \infty}{\frac{e^n}{(\sqrt{2\pi n})(\frac{n}{e})^n}} = \lim\_{n\rightarrow \infty}{\frac{e^{2n}}{(\sqrt{2\pi n})n^n}} = \lim\_{n\rightarrow \infty}{\frac{1}{\sqrt{2\pi n}}\frac{e^{2n}}{n^n}}$$

Since $\lim\_{n\rightarrow \infty}{\frac{1}{\sqrt{2\pi n}}} = 0$ we only need to calculate $$\lim\_{n\rightarrow \infty}{\left(\frac{e^2}{n}\right)^n}$$ The function $\frac{e^2}{n}$ decreases faster than any function $c^n$ where $0 \< c \< 1$ for sufficiently large $n$s (as $n$ goes to infinity), and so $\lim\_{n\rightarrow \infty}{\left(\frac{e^2}{n}\right)^n} = 0$.

**Regarding Quazi Irfan's comments about Matlab graph**
I am not a Matlab user, but these are plots for $e^x$ and Stirling approximations of $n!$ using Wolfram script: `plot (1\sqrt(2*pi*x)*(x/e)^x) from 0 to 6, plot(e^x) from 0 to 6`

As you see $n!$ overtakes $e^n$ when $n=6$.

---
Tags: asymptotics
---


title: Clustered index is dense or sparse?

text:
# Question
Title: Clustered index is dense or sparse?
I am confused about clustered index is dense or sparse. I searched for that, sources saying it is sparse, but can be dense also. What is it exactly?

# Answer
Clustering index is applied when records are physically ordered on a nonkey field(called clustering field). As clustering field is nonkey so there can be more than one distinct record for a single clustering field value.

The strategy of clustering index is: There is one entry in the clustering index for each distinct value in the clustering field, containing the value, and a pointer to the first block in the data file that has a record with that value for its clustering field.

So clearly it is a sparse index.
> 1 votes

# Answer
Clustered indexing can be both dense and sparse. Lets see how

Quick recap: clustered indexing is done on non key attributes and it is sorted according to that attribute. Idea behind clustered indexing is to have one entry per unique value, as once we have pointer to that location we can find other entry for the value as it is sorted.

Case 1: non key attribute has unique value

It will be dense indexing as we have to give every value entry in index table

Case 2: non key attributes isn't unique

In this case we can have just one entry for every unique value in index table.
> 2 votes

---
Tags: terminology, database-theory
---


# Question
Title: Proof: "If the list is then k-sorted for some smaller integer k, then the list remains h-sorted"
> Shellsort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, considering every hth element gives a sorted list. Such a list is said to be h-sorted. Equivalently, it can be thought of as h interleaved lists, each individually sorted. Beginning with large values of h, this rearrangement allows elements to move long distances in the original list, reducing large amounts of disorder quickly, and leaving less work for smaller h-sort steps to do. **If the list is then k-sorted for some smaller integer k, then the list remains h-sorted.** Following this idea for a decreasing sequence of h values ending in 1 is guaranteed to leave a sorted list in the end.

\[Source\]

*What is the mathematical proof for the quoted claim (in bold)?*

**An attempt at the proof** (for the case when number of elements is $2n+1$):

---

My initial array is $A = \\{x\_0, \cdots, x\_n\\}$ and i have $x\_0 \< x\_n$. Say that after first pass $x\_0$ switches place with $x\_m$, so the final array $B$ starts with the entry $x\_m$ regardless of the position of $x\_0$ (which can further switch place with $x\_{2m}$ and so on). Thus, $x\_m \< x\_0$. Now, in the final pass $x\_n$ can switch place with $x\_k$ (which, before the last pass, is in the $(n-m)$-th position in the array). We don't care about $k$, but we just know that $x\_n \< x\_k$. So the last entry in the final $m$-sorted array $B$ is $x\_k$. Sum it up: $x\_m \< x\_0 \< x\_n \< x\_k$.

That means $B$ is $n$-sorted. If we assumed the switchings of $x\_0$ and $x\_n$ didn't happen during $m$-sorting, we are trivially done, because the starting and final entries of $B$ are $x\_0$ and $x\_n$ respectively, and since $x\_0 \< x\_n$, $B$ is $n$-sorted.

Say $A = \\{x\_0, \cdots, x\_n, \cdots, x\_{2n}\\}$ is $n$-sorted. We can assume the subarray $\\{x\_0, \cdots, x\_n\\}$ is $m$-sorted WLOG and because of what we proved earlier. Suppose now that while $m$-sorting, $x\_n$ and $x\_{n+m}$ are switched; then $x\_{n+m} \< x\_n$. And then on the last entry, $x\_k$ (in the $2n-m$ th position) and $x\_{2n}$ are switched. Then $x\_{2n} \< x\_k$.

After the $m$-sorting is over, the $n$-gap subarray starting at $x\_0$ is $\\{x\_0, x\_{n+m}, x\_k\\}$. We have $x\_0 \< x\_m \< x\_{n+m} \< x\_n \< x\_{2n} \< x\_k$, where $x\_m \< x\_{n+m}$ is because $A$ is $n$-sorted.

So, this is proof that if a $2n+1$ array is $m$-sorted after being $n$-sorted, it remains $n$ sorted.

---

However, I don't know how to generalize that for any size of array.

# Answer
the claim follows easily from a careful definition of "*k*-sorted". *define k-sorted* as "for all *i* there does not exist a *j \> k* such that for two elements in the list *a\[i+j\] \< a\[i\]*." then if a list is *k*-sorted, it is h-sorted for *h \> k.*

to look into deeper/ more general theory realize that *k-sorted* is a *"measure of disorder"* eg as in question how to measure sortedness. see this paper a survey of adaptive sorting algorithms, / Castro, Wood, measures of disorder, sec 1.2. *h-sorted* appears to be equivalent to measure #1, *Dis*, "largest distance determined by an inversion".
> 2 votes

---
Tags: algorithms, algorithm-analysis, sorting, correctness-proof
---


# Question
Title: Closed (visited) list in state-space search - How do I make it efficient?
As part of an assignment for an AI class that I'm taking, I'm need to solve a puzzle on a 4x4 grid using breadth-first search (each element can take on 12 different values). There is a maximum of 4 moves for each state. Needless to say, after 30-or-so moves, the number of nodes (each representing a state) in the queue gets too large for most (any?) computer to handle, since many nodes are duplicates.

The solution, as far as I know, is to add all visited nodes to a "visited list." This makes it possible to compute without running out of memory, but it takes forever. Why? Because for each node that I add, I have to make sure that it's not in the list of visited nodes. For a somewhat complex puzzle, this list can get really long. Let's say the list gets to 500000 nodes, which is feasible. That means that for every new node I add to the queue, it needs to be compared to 500000 nodes to make sure that it isn't identical to any node in that list. This takes a really long time to compute. It solves the problem, but I'm pretty sure I have the wrong idea about how to approach this to actually make it efficient.

I know BFS usually isn't a very good approach to these kinds of problems, but it's part of the assignment. It's only about actually solving the puzzle, but I'm interested in knowing if there is a way to make it more efficient. In general, I mean. I'm sure that I could tailor the program to make it solve this specific puzzle much faster, but what I want to know if there's some idea that could be applied to all problems.

Any help is greatly appreciated!

# Answer
> 2 votes
Use a hash table to store the visited list. Searching the list should take $O(1)$.

---
Tags: graphs, trees, artificial-intelligence
---


# Question
Title: Check if current interval is overlapping some intervals, or is being overlapped
Let's say we have array of $K$ integers, and we have given $N$ intervals in the form $l\_{i}, r\_{i}$, both inclusive, the interval $i$ means that all elements in the range $\[l\_i, r\_i\]$ are covered. Our task is to check for any of those $N$ intervals is the interval $i$, or the range $\[l\_i, r\_i\]$ being covered twice or more. Look in the examples to make it clear.

**Example**

$N = 3$, we have the intervals $I = \\{ (1, 3), (4, 6), (1, 7) \\}$. Let's illustrate the intervals

```
1 2 3 4 5 6 7 8 9 10...
-----               -> Interval 1
      -----         -> Interval 2
-------------       -> Interval 3

```

We can see that the elements that are being covered by Intervals 1 and 2, are already covered with Interval 3, so we should return one of those indexes.

Please note that $K = 10^9$, so we cannot store the whole array.

**What I think**

If we were able to store the whole array of $K$ members, we could easily solve with lazy propagation, and range minimum queries, but since we cannot do that, I think that we should create dynamic segment tree where we will keep only the ranges we need to store the value for.

For example, if we need only the range $\[1, 128\]$ we do not need to store the ranges $\[1, 63\]$ and $\[64, 128\]$. This will save memory and time, but is it enough fast to solve this problem, and what will be the time complexity for this solution if we assume that $N \leq 10^5$.

# Answer
Hint: Sort $\\{l\_1,r\_1,\ldots,l\_N,r\_N\\}$ and replace the sorted list with $1,\ldots,2N$ to effectively reduce $K$ to $2N$.

(There might be better ways of solving the problem, but this reduction at least gets rid of the dependence on $K$.)
> 1 votes

---
Tags: search-algorithms, arrays, search-trees, intervals
---


# Question
Title: Not able to devise a concrete solution for the given graph query
I was trying to solve the following problem:

You are given a grid of size N×N that has the following specifications:

Each cell in the grid contains either a policeman or a thief.

A policeman can only catch a thief if both of them are in the same row. Each policeman can only catch one thief.

A policeman cannot catch a thief who is more than K units away from the policeman.

Write a program to find the maximum number of thieves that can be caught in the grid.

example:

N=3,K=1

P T P

T T P

T P T

Answer:3

I tried a simple BFS solution but my code if failing in which there are alternative P and T,am not able to handle this case with BFS.

My solution:solution(Its a bit lengthy,so didn't paste it here.)

It would be really helpful and highly appreciating if someone could suggest some algorithm or pseudo code for this problem statement.

PS:This was the question of this test.It was a timed test, couldn't solve it.

Thanks.

# Answer
Your problem is very similar to interval scheduling, and it seems it can be solved similarly using a greedy approach. Note first that you can solve each row separately. For each row, you scan the row from left to right. Assign each policeman to the leftmost thief that he can capture and isn't already taken (if any). Intuitively, this should work, and you can try proving that it does using the standard proof method of comparing the greedy solution to an optimal one.
> 1 votes

---
Tags: graphs, data-structures
---


# Question
Title: How is the definition of monads in category theory equivalent to the definition in functional programming?
In Haskell, `Monad` is a class of type constructors which act on types that have the following functions implemented:

```
(>>=)  :: m a -> (a -> m b) -> m b
(>>)   :: m a ->       m b  -> m b
return ::   a               -> m a

```

and they satisfy the following "laws:"

```
return a >>= f      = f a
m        >>= return = m
(m >>= f) >>= g = m >>= m >>= (\x -> f x >>= g)

```

I understand why a type with these functions implemented with those constraints is useful, because I've used them. But to be completely honest, I'm interested in pure mathematics over programming, so I want to understand the category theoretic origins of monads.

Monads in category theory seem very different, they are ordered triples $\langle T, \mu, \nu\rangle$. Where $T$ is an endofunctor on a given category $C$, $\mu : 1\_C \rightarrow T$ is a natural transformation as is $\nu : T\circ T \rightarrow T$ such that they all satisfy conditions reminiscent of the one's for Haskell monads. It seems like `return`, which I understand to be the type constructor for an instance of monad, is the endofunctor $T$.

In essence I want to understand which functions are which natural transformations, and why, but I also want to understand why `return` is an endofunctor, acting on a category, even though it seems like most types in Haskell are treated as objects.

I was once watching Bartosz Milewski lecture and he said that monads can be thought of as "monoids on the category of endofunctors." I stopped watching because I didn't know what monoids were at the time. But now when I think "monoid on the category of endofunctors" I think "The set of endofunctors on a category under composition." But I don't see how an object like this could relate to the definition of a monad, so if someone could explain that as well it would be greatly appreciated.

# Answer
> 9 votes
The Haskell monads are known as Kleisli triples in mathematics. I am guessing you're coming from the Haskell land, so let me just put down the translations between the two formulations in Haskell (I define everything from scratch on purpose and avoid clashes with standard notation):

```
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE FlexibleInstances #-}

class MyMonad t where
  fun :: (a -> b) -> (t a -> t b) -- functorial action, known as fmap
  eta :: a -> t a
  mu :: t (t a) -> t a

class KleisliTriple t where
  ret :: a -> t a
  (>>==) :: t a -> (a -> t b) -> t b

instance KleisliTriple t => MyMonad t where
  fun f x = (x >>== (ret . f))
  mu x = (x >>== id)
  eta = ret

instance MyMonad t => KleisliTriple t where
  ret = eta
  (>>==) x f = mu (fun f x)

```

There's a bunch of equations to be verified, but they all work out, which is not to say that you should trust me or anyone else, work them out, it's a good exercise. Actually, you should try to reconstruct things by yourself. Take the code above and delete the two instances. Then try to reconstruct their definitions.

As for your question about monads being monoids in the endofunctor category, you'll just have to unfold all the definitions in the privacy of your own mind. I can give you a roadmap, but until you pick up pencil and paper and go through it all by yourself, it's not going to click.

Recall that a monoid is given by a set $T$, a multiplication operation $\mu : T \times T \to T$, and an element $\eta \in T$ such that

1. $\mu (x, \eta) = x$
2. $\mu (\eta, x) = x$
3. $\mu (\mu (x, y), z) = \mu (x, \mu (y, z))$

$\newcommand{\CC}{\mathcal{C}}$ $\newcommand{\pair}\[1\]{\langle #1 \rangle}$ This can be generalized as follows. Consider a monoidal category $\mathcal{C}$. It has a tensor product $\otimes$ which behaves a little like ordinary binary products, and it has a special object $I$ which is a unit for the tensor. A monoid object in the monoidal category $\CC$ is given by the following data:

* an object $T \in \CC$
* an arrow $\mu : T \otimes T \to T$
* an arrow $\eta : I \to T$

subject to the laws that correspond to the three laws above. I am not going to reproduce the laws here, you can find them here.

If we take $\CC = \mathsf{Set}$, $A \otimes B = A \times B$, and $I = 1$ then we recover the usual notion of monoid.

Now let $\CC$ be any category (no monoidal structure required). The functor category $\CC^\CC$ is monoidal if we take the tensor to be composition of functors $F \otimes G = F \circ G$, and the unit the identity functor $I = \mathsf{Id}\_{\CC}$. What is a monoid object in $\CC^\CC$? It is given by the following data:

* a functor $T : \CC \to \CC$
* a natural transformation $\mu : T \circ T \to T$
* a natural transformation $\eta : \mathsf{Id} \to T$

subject to some laws. When we unfold those laws we get, you guessed it, precisely the laws for a monad.

---
Tags: functional-programming, category-theory
---


# Question
Title: How is the concurrent tracking of "state position" in NFA's typically modelled?
Conceptually, to track the multitude of "state positions" arising in an NFA while it is processing a given input string, a quantitative notion of memory/cache/storage is required per "fork" of execution over the automaton, for keeping track of the states where the computation is currently "at".

What is the typical theoretical treatment, regarding the complexity of this degree of concurrency?!

# Answer
> 2 votes
The theoretical treatment is just to say "It's what happens: that's what nondeterminism is." The machine accepts if there's any computational path that finishes in an accepting state.

Anything about memory, caches or concurrency is a matter of implementation. The simplest implementation is to keep a vector of Booleans that records whether or not the machine "could be" in each of the states at the current step of the computation.

---
Tags: complexity-theory, finite-automata, concurrency
---


# Question
Title: Big O - Equivalence: "Standard" definition vs Limit definition
This question is related to: Landau Notation, Definitions: Limits vs. Cormen's.

Consider functions $f, \ g : N \rightarrow R^{\geq0}$.

For small-$o$, the definition: $$f(n)\in o(g(n)) \iff \forall c\>0,\exists n\_0\>0, \forall n\geq n\_0: f(n) \< c \ g(n)$$

Can also be expressed as a limit (i guess this assumes the limit exists): $$f(n)\in o(g(n)) \iff \lim\_{n\to\infty}\frac{f(n)}{g(n)}=0 $$

This can be verified introducing the definition for $\lim\_{n\to\infty}$ on $N$, and then both definitions are identical.

Now, the "standard" definition for big-O would be something like (near exactly to Cormen's, except the codomain here is $R^{\geq0}$): $$f(n)\in O(g(n)) \iff \exists c\>0,\exists n\_0\>0, \forall n\geq n\_0: f(n) \leq c \ g(n) \qquad (1)$$

Im trying to see if the following is true (again, this assumes the limit exists): $$f(n)\in O(g(n)) \stackrel{?}{\iff} \exists c\>0: \lim\_{n\to\infty}\frac{f(n)}{g(n)}=c$$

Im not sure both directions of the equivalence are true. More specifically, i am having trouble with the $\Rightarrow$. According to this general answer, both directions should be true for $\Theta(g(n))$, wich is stronger than $O(\\\_)$. On the contrary, this answer (for roughly the same question, but in math SE) says big-$O$ cant be defined in that way (it was downvoted).

So, the questions are:

1. How exactly def (1) implies the $\lim$ definition?:

$$\forall \epsilon\>0,\exists n\_0\>0, \forall n\geq n\_0: \left| \frac{f(n)}{g(n)}-c\right| \< \epsilon$$

2. Is the above still true considering generic functions $f, \ g : X \rightarrow R^{\geq0}$, where $X$ is some reasonable domain, maybe $Z$, $N^k$ or even $R^k$ (although reals are not turing-computable, im thinking in algorithms in the more general sense possible).

# Answer
> 0 votes
If $f = O(g)$ then there exists $C\>0$ such that for large enough $n$, we have $f(n)/g(n) \leq C$. Hence under mild assumptions, $$ f = O(g) \Longleftrightarrow \limsup\_{n\to\infty} \frac{f(n)}{g(n)} \< \infty. $$ As Raphael mentions in a comment to your post, your definition is symmetric in $f,g$ and so is more appropriate for $\Theta$.

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


# Question
Title: How to find n-1 complete matches for bipartite graphs that are related (speed-date)?
How can one assign **n** people pairwise to **n-1** tables, in a speed-date fashion, such that no two persons meet twice and each person is at each table exactly once? Does this problem have a name?

### The problem in full

Given **n** people (**n** is even), assign them in pairs in **n-1** rounds. Each round represent a list of **n/2** pairs, each pair being two individuals that have not met earlier.

For each round, find a match between the **n/2** pairs and **n-1** tables, so that every pair are assigned a table. The tables are unique. Through all **n-1** rounds, an individual should meet each other individual exactly once, and be at each table exactly once.

### What have I tried?

Here is the naive bipartite matching algorithm I've created so far:

1. Create rounds using the round-robin tournament scheduling.
2. Represent each round as a bipartite graph, pairs vs tables.
3. For each round, find a match.
    * For each player, remove table matched in this round.

In pseudo:

```
n = 6
tables = [1, 2, 3, 4, 5]
players = [{'i': 1, 'tables': copy(tables)}, {'i': 2, 'tables': copy(tables), ...]
rounds = roundRobin(players)
# each round has a list of pairs
# each pair is two players
# [
#     [[1,6], [2,5], [3,4]],
#     [[1,2], [3,6], [4,5]],
#     ...
# ]
matches = []
# keep matches

for round in rounds:
    match = hopcroft_karp(round, tables)
    # pair 1 to table 1, ...
    # [ [1, 1], [2, 2], [3, 3] ]

    if len(match) !== len(round):
        # TODO: backtrack
    else:
        add match to matches
        for edge in match:
            pair = round[edge[0]]
            table = edge[1]
            removeTable(pair[0], table)
            removeTable(pair[1], table)

```

### Example

For some **n**, there is no solution. For example **n = 4**. I'm unsure for which **n** the problem has solutions. Here is **n = 4** as an example:

```
People: 1, 2, 3, 4
Tables: A, B, C

Round 1: A:1,2 - B:3,4
      In round 1, we can assign tables at random, because
      the problem is the same with renaming tables.
Round 2: C:1,3 - ?:4,2 <-- not possible
      4 has already been at table B.
      2 has already been at table A.
      Table C is taken by pair 1,3.
Round 3: ?:1,4 - ?:2,3 <-- same as round 2

```

# Answer
Your problem seems to be the same as that of constructing a Room square. Let me quote from The existence of Room squares by Mullin and Wallis:

> A Room square of side $2n+1$ is a $2n+1$ by $2n+1$ array of cells and a set $S$ of $2n+2$ objects called symbols which satisfy the following conditions:
>
> (i) Every cell of the array is either empty or contains an unordered pair of distinct symbols from $S$.
>
> (ii) Each symbol occurs in every row and column of the array.
>
> (iii) Every unordered pair of symbols occurs precisely once in the array.

Mullin and Wallis state that a Room square of size $v$ exists for all odd positive $v$ except for $v=3,5$. This explains why your construction for $n=4$ (which corresponds to $v=3$) wasn't successful.

To construct a Room square, look into the article Construction of Room Squares by Stanton and Mullin.
> 2 votes

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


# Question
Title: proving that $P\ne NP$ under an assumption
Suppose that $P^{SAT} \not\subseteq coNP$. Prove that $P\ne NP$.

What I did:

Suppose that $P=NP$. Then, $P = coP = NP = coNP$.

We know that $P^P = P$.

Then, by assumption: $P^{NP} = NP = coNP$

Since $SAT$ is $NP$-complete we get: $P^{SAT} = coNP$ in contradiction to the assumption.

So $P\ne NP$.

I've been told that my proof is false, but I don't understand why.

# Answer
Here is a more direct proof. Suppose that $P=NP$. In particular, SAT can be solved in polynomial time. Therefore $P^{SAT} \subseteq P^P = P \subseteq coNP$.
> 3 votes

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


# Question
Title: Regular expression with out the substring bab or abb?
I'm having a problem coming up with a regular expression for a language L = {a,b} with out the substring bab or abb? I can come up with the one for just one substring, like

a\*(b\* aaa\* )\* b\* a\* to eliminates the bab and b\*(a+ab)\* to eliminates the abb substrings.

But putting them together is a huge animal :(

# Answer
There are a couple tricks required to get this right.

First, this particular problem is a lot easier if you approach it backwards, starting at the end of the sting.

`(abb,bab)` is an exhaustive list of all the cases in which `b` is preceded by 2 different letters. If you want to exclude these cases, you just have to ensure that `b` is preceded by less than 2 letters, or a double letter.

Second, notice that these rules imply that if there are 2 `b`s in a row, then they must be preceded by `b` all the way to the start of the string. Otherwise the second-to-first `b` will be preceded by `ab`.

Working from the end, then, we can have a free mixture of `a` and `aab`, and then there are only a few ways to get to the beginning of the string when we encounter a `b` outside of that pattern:

```
(ab|b*)(aab|a)*

```
> 2 votes

# Answer
Thanks for the help, i came up with a solution, although I'm not 100% sure:

0\*(1+000\*)0\*+(1\*0\*)

Here can use jflap to test a few strings.
> -3 votes

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


title: Aggregate planning with inventory

text:
# Question
Title: Aggregate planning with inventory
I am lost in formulating a mathematical model for my linear integer program. My problem is; how to include inventory and backlogging.

The following is given:

* 1100 units can be produced each month
* Unit production cost = \\$7
* Inventory unit cost = \\$2
* Annual expense = \\$10.000
* Sales unit price \\$12
* We have given the demand for 12 month and need to plan for 12 month
* If demand is not met in one month, it will be transferred to next month (backlogging)
* All demand should be met in the end of the year
* The sum of all demand = 12.345 unit

We want to maximize the profit

\begin{align} \max \sum\_{i=1}^{12} x\_i 12 - 10.000-\sum\_{i=1}^{12} x\_i 7 - \sum\_{i=1}^{12} y\_i 2 \end{align} where $x\_i$ is the amount produced each month, for i=1,...,12 and $y\_i$ is the amount of inventory each month. I have defined the following constraints:

\begin{align} x\_i \leq 1100 \\ \sum\_{i=1}^{12} x\_i = 12345 \end{align}

So if we have $d\_i\geq x\_i$ we backlog the demand, and if $x\_i \geq d\_i$ we put it in inventory. \begin{align} if: d\_i \geq x\_i : b\_i = d\_i-x\_i+b\_{i+1} \\ if: x\_i \geq d\_i : y\_i = x\_i - d\_i + y\_{i-1} \end{align} where $b\_i$ is the amount backlogged and $d\_i$ is the demand.

But this is not correct, since the inventory constraint should be smaller if we take some of it to meet the demand that exceeds the amount we can produce (if we have something backlogged), and if we have some inventory, then we don't need to backlog it. I really hope that someone can help me formulate it correctly.

# Answer
> 1 votes
Your objective-function seems to only concern inventory (that's the only variable aspect of your problem). Indeed $\sum x\_i =12345$ is constant, your profit, excluding inventory cost, will be $5$ times this in any case ($12 - 7$). Your objective can be written more simply as $\min \sum y\_i$

$b\_i=\max\\{0, d\_i-x\_i-y\_{i-1}\\}$ and $y\_i=\max\\{0, x\_i+y\_{i-1}-d\_i\\}$ should be the additional constraints. If production + previous inventory is not enough to satisfy demand, you get a backlog at period $i$ and inventory at $i$ is what remains after satisfying the current demand with the current production + previous inventory.

So $b\_i\geq d\_i-x\_i-y\_{i-1}$ and $y\_i\geq x\_i+y\_{i-1}-d\_i$ should do.

Since $y\_i$ are to be minimized, these variables would equal their lowest feasible bound ($0$ or the difference above).

You will just pay $\\$2$ for every unit you produce above demand on a given period. However, from an inventory management point of view, the cost of inventory in your model seems unusually simplistic. A more realistic cost for inventory would consider a holding/carrying cost (cost of holding one unit of inventory for one unit of time) and an ordering cost (cost of ordering raw material or components). The difficulty of inventory problems is typically determining when and how much to order to find the best trade-off between these two costs.

PS. It may make sense at the aggregate level, and intermediate-planning time horizon, to make such a simplification regarding inventory costs. However, aggregate planning and inventory management are two strategic problems in their own rights, over two different time-horizons. They cannot be easily solved by one simple, integrated model (mostly because of different levels of uncertainty in demand over the two time-horizons and at the aggregate vs individual level).

---
Tags: optimization, linear-programming, integer-programming, planning
---


# Question
Title: Simple (non-mathematical) definition of polynomial time?
Computational Complexity Theory is complex. My understanding of polynomial time is in relation to other time complexity classes, such as non-deterministic polynomial time. This is fine for engineers and mathematicians, but I'm looking for a simple definition of the term, suitable for laypeople.

* Would it be incorrect to cast polynomial time as *"time measured in (computational) operations?"*

Obviously there would be subsequent qualifications for different time complexity classes, and time complexity may be more properly a ratio based on the problem size, but again, that's a bit more complex than what I'm looking for here.

# Answer
> 9 votes
"Polynomial time" is a statement about the running time of an algorithm. In theory, the running time of an algorithm is a count of the number of basic operations it does. This is expected to be proportional to the time it takes for the algorithm to run on a computer. Polynomial time means that the running time is at most some (unspecified) polynomial in the size of the input; e.g., proportional to the square of the input size, or cube, or something like that. Polynomial-time algorithms are often efficient enough to implement in practice.

See https://en.wikipedia.org/wiki/Time\_complexity#Polynomial\_time and https://en.wikipedia.org/wiki/Cobham%27s\_thesis.

# Answer
> 40 votes
Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size.

Exponential time algorithms are algorithms whose running time increases by a constant factor when the input size increases by 1.

For laypeople you can perhaps identify NP-complete problems with problems solvable only in exponential time, although, as we know, this is wrong on many counts.

# Answer
> 37 votes
> Would it be incorrect to cast polynomial time as "time measured in (computational) operations?"

Yes. Completely incorrect.

"Time" does indeed mean "time measured in (computational) operations" but you've not translated "polynomial" at all. It's like translating "twelve days" as "time measured in number of rotations of the earth on its axis." That's exactly what what "day" means, but what happened to "twelve"?

Polynomials are inherently mathematical objects and I doubt there's any way of explaining them without using mathematics. You can explain that polynomial algorithms are usually regarded as being reasonably efficient, but that's a consequence of what a polynomial relationship is, not an explanation of it.

# Answer
> 1 votes
There's really not much you can do to provide simple definitions of those problem spaces. Remember that problem spaces like P and NP are defined by asymptotic behavior as some number `n` goes to infinity. There are no layman situations where going to infinity is useful, and the precision needed to define it that way is brutal.

As such, I find its easiest to describe P and NP as "fast" and "slow," and then use the practical example of cryptography because it's interesting to people. I start with NP (because there are fast and slow P algorithms, so I want to anchor their concept of "slow" to that of exponential time before bringing in P). Everyone has dealt with some sort of geometric growth somewhere, even if its just compound interest, so there's something to start from.

Once I think they have some idea of exponential time, I introduce the cryptography link. One of the goals of cryptography is that adding 1 bit to a key doubles how long it takes someone to break it. The essential part is to connect the idea that adding work to the sender/receiver multiplies the amount of work needed by the attacker.

With that, I can then bring up Moore's law, which very roughly says computing power doubles every 18 months. That means my attacker is able to do twice as much work if he can wait for the hardware to catch up. When his attacking capability doubles, I have to add a bit. Then he doubles again, and I add a bit. Then I can show just how asymmetric this game is -- every time they do a *massive* amount of extra work, I have to do just a little extra work to keep things even.

Now I can teach polynomial time as algorithms that run faster than exponential time. This is a bit of a simplification, but for a layman I think it's okay. If my crypto algorithm were polynomial time, as my attacker's computational speed got better, I'd have to be adding bits quicker and quicker, bogging down the system. *Everyone* knows what it means when a computer runs slow!

---
Tags: complexity-theory, terminology, time-complexity
---


# Question
Title: Proving that $ (a \cup b)^* = (b^*(a\cup\lambda)b^*)^*$?
How would I prove that these two regexes are equal to one another? $$ (a \cup b)^\* = (b^\*(a\cup\lambda)b^\*)^\*$$

I'm permitted to use the following regular expression identities.

# Answer
One of the equalities 12 tell us that now $(u\cup v)^\* = u^\*(vu^\*)^\*$. Applying this to the last expression we obtain $(b\cup (a\cup\lambda))^\*$.

Also $(u\cup \lambda)^\* = (u^\*\lambda^\*)^\* = (u^\* \lambda)^\* = (u^\*)^\* = u^\*$.

Do you have associativity of $\cup$ so that $(b\cup (a\cup\lambda))^\* = ((b\cup a)\cup\lambda))^\*$? It should be a basic property.
> 3 votes

---
Tags: regular-expressions, proof-techniques
---


title: how to convert any fraction to decimal

text:
# Question
Title: how to convert any fraction to decimal
So for a project I am working on. I need to take a string representation of a floating point number, lets say "1.5" and do arithmetic on it with another floating point number. The catch is I cannot use floats to do this, since it specifically says in the requirements for my homework that I can't do this. How I am supposed to do something like add or subtract these numbers is break the string apart into it's characteristic (1) and it's mantissa(5). so in the program, the program will be represented as 1/2. However, if I wanted to add 1.5 with 1.3, 1/3 goes on forever. Thus making it impossible to convert 1/3 to 1/(some power of 10) and figure out how to add everything together. Is there an algorithm that can deal with cases of division like 1/3?

# Answer
> 1 votes
You should implement rational numbers yourself. Store number as two integers. Use the greatest common divisor to factor out superflous representation. Literally write school algorithms for rational numbers - find common denominator for addition and then normalize number. At the end convert it to decimal representation with fixed precision. Namely use symbolic calculation as long as you can.

From your example:
$\frac{1}{3} + \frac{1}{5} = \frac{5}{15} + \frac{3}{15} = \frac{8}{15} \approx 0.5333$

If your task really requires to convert it to string at the first step, then you have to assume some precision, e.g. four numbers in decimal expansion, and then write your own code to operate on numbers. The exact decimal expansion is not always possible, as you have already realized, so $\frac{1}{3}$ would expand to "0.3333" (arbitrary length from my example. It may seem weird at first, but the floats are also inexact, with precision given by fixed length representation (e.g. 64, 80, 128 bits).

$\frac{1}{3} \approx 0.333; \frac{1}{5} \approx 0.2000$
So
$0.3333 + 0.2000 = 0.5333$
It gives the same approximate result.

---
Tags: algorithms, floating-point
---


# Question
Title: Print maximum frequency number in an array(with slight modification)
There is an integer array and 2 variables Q and M.The output required is the number which has the maximum frequency in the array, but the catch is that each number in the array can be increased/decreased by M and that too Q number of times.

In case of multiple answers print the first one.

eg:

array:1,2,3,4 and Q=1,M=1

Answer:3 ,as the array can be transformed into 2,2,2,4 (here 2 appears 3 times in this array, adding 1 in 1 and subtracting 1 from 3.)

A hashtable can be used here,but can't understand how to handle the addition and subtraction of each number of the array.

Can anyone please suggest an approach for that part?

Thanks.

# Answer
Start by sorting the array. Now go over the array using four pointers, left, center left, center right, and right. The two central pointers bracket all the occurrences of some value $x$. The left pointer points at the leftmost value which is at least $x-M$, and the right pointer points at the rightmost value which is at most $x+M$. Using the positions of these pointers you can calculate the maximum frequency of $x$.

Traversing the array should take linear time, so the entire algorithm takes time $O(n\log n)$.

For a possibly simpler solution, you can sort the array and then use a single pointer to traverse it. Treat this pointer as one of the central pointers from the previous algorithm, and find the locations of all other pointers in logarithmic time using binary search. Traversal now takes time $O(n\log n)$, but this doesn't increase the asymptotic running time of the algorithm.
> 0 votes

---
Tags: algorithms, arrays, hash-tables, c++
---


title: positivity condition in Coq/CIC

text:
# Question
Title: positivity condition in Coq/CIC
I am recently learning the theory behind Coq and learnt that positivity condition guarantees termination of the program. But my question is, what would you think of the following definition?

```
Inductive t : Set := b : t | c : ((t -> unit) -> unit) -> t.

```

Sure it won't compile in Coq, but would it jeopardize termination guarantee? More precisely, in this definition, `t` is in a positive position as well, isn't it? So can I say theoretically speaking this should have also been a valid definition? Otherwise do you have any counter example?

My thought is, `(t -> unit) -> unit` should be isomorphic to `t` according to Yoneda lemma so it should be pretty safe, isn't it?

# Answer
> 6 votes
The positivity condition is not there just so that "programs terminate", as you put it (what programs?), but to make sure the type is well defined in the first place. The inductive definitions define the *smallest* type satisfying an equation. That is, we put into the type only those things which are prescribed by the clauses of the definition, and no arbitrary garbage. (Non-normalizing terms count as garbage, and I think that's what you meant when you spoke of terminating programs.)

Let us take a step back and think where the inductive definitions come from. They are solutions to *type equations*. Here is a type equation: $$N = \mathtt{unit} + N.$$ What could $N$ be? We might be thinking that it *must* be the natural numbers, since every element of $N$ is either $\mathtt{inl}(\mathtt{tt})$, which is a fancy way to say "zero", or it is of the form $\mathtt{inr}(n)$ for some $n : N$. But this need not be the case! For example, $N$ could *also* contain a special element $\infty$ satisfying $\infty = \mathtt{inr}(\infty)$. It could also contain an extra "fake zero" $\mathtt{Z}$, together with its successors $\mathtt{inr}(\mathtt{Z})$, $\mathtt{inr}(\mathtt{inr}(\mathtt{Z}))$, ... There are *many* solutions to the above equation.

The smallest solution is called the *inductive type*, and the largest one the *coinductive type*. I am skipping technicalities about what "smallest" and "largest" mean precisely (they are the "initial algebra" and "final coalgebra", respectively), but I hope you get the point.

In order for us to say that we have a well-defined inductive type, we need to know that the smallest solution to the type equation actually exists. In fact, it does not always exist, sometimes there can be several incomparable solutions, or none at all. The positivity condition in Coq and CIC ensures that a smallest solution exists. It's not the only possible condition one could come up with, and there are variants, but for the purposes of a proof assistant we need something that makes sense computationally, and can actually be verified by a type checker (for instance, it wouldn't do to say that an inductive definition is valid if it defines a $\kappa$-accessible functor for some cardinal $\kappa$, and have the proof checker look for $\kappa$ – hmm, that's an interesting thought).

If we now look at your proposed definition

```
Inductive t : Type := b : t | c : ((t -> unit) -> unit) -> t.

```

the question to be asked is: how do you know that the smallest solution exists? Somebody proved that the strict positivity requirement ensures the existence, but your definition falls outside that criterion. You need to provide evidence that there is such a type. The evidence must be a well argued explanation of what the terms of `t` are that they do not break strong normalization of CIC. You might as well succeed, and there is such a type. The next question then is how do you propose to incorporate your argument into a type checker as a useful algorithm. It's probably not worth the trouble.

Just to show you how problematic these things are, how about the type

```
Inductive t : Type := c : ((t -> bool) -> bool) -> t.

```

Is it still totally obvious that there is a smallest solution? We're trying to solve the type equation $$T = (T \to 2) \to 2.$$ It has no solution in set theory.

---
Tags: programming-languages, logic, coq
---


# Question
Title: Is this DO LET sugar considered pure Lambda calculus and nullipotent / side-effect-free?
I'm thinking these familiar concepts of `DO` and `LET`/`LET*` in the context of Lambda Calculus (LC).

`LET` is an abbreviation for this LC expression:

```
(LET a 1 b 2 e) = (λ a . (λ b . e) 1 2)

```

and `LET*` is an abbreviation for this LC expression:

```
(LET* a 1 b 2 e) = (λ a . (λ b . e 2) 1)

```

where `e` is the body of the function. `LET*` just enables to use former variable inside latter variable in the following way:

```
(LET* a 1 b a e) = (λ a . (λ b . e a) 1)

```

`DO` is an abbreviation too and can be used in conjunction with LET's to achieve same than `LET*`:

```
(DO (LET a 1) (LET b 2) e) = (λ a . (λ b . e 2) 1)

```

So I have three different shorthands to construct LC expressions. Now, my questions is that is this syntactic sugar throwing me out from pure LC (or functional programming in general sense) and am I introducing side effects by this syntax?

In a way it looks like it, but on the other hand these three shorthands are only abbreviations and they translate to Lambda Calculus expressions that are well defined and reducible as any LC expressions.

# Answer
Anything that can be encoded in the pure lambda calculus, as you realize in the last paragraph, can not have side effects. Otherwise, the lambda calculus itself would be able to express those side effects as well.

However, note that your encoding looks a bit weird. For instance,

```
(LET a 1 b 2 e) = (λ a . (λ b . e) 1 2)

```

does not bind `1` to `a` and `2` to `b`. You probably want instead

```
(LET a 1 b 2 e) = (((λ a . (λ b . e)) 1) 2)

```

which does the correct binding. The other encoding should be fixed similarly.

I would suggest you "test" these encoding by performing $\beta$ steps. If you don't reach $e\\{1/a,2/b\\}$ something looks wrong.
> 2 votes

---
Tags: lambda-calculus, syntax
---


# Question
Title: What is the bit complexity of Gaussian eliminaton over $\Bbb F_q$?
Given matrix $M\in\Bbb F\_q^{n\times n}$ with rank $r$ what is the complexity of converting to row-echelon form?

> Is it $O(n^3\log q)$ or $O(n^3q)$ bit operations?

Technically $O(n^3)$ row operations in $O(\log q)$ bit words should be $O(n^3(\log q)(\log\log q)^2)$ bit operations in worst case when $q$ is prime.

What I am confused about is

1. when $q$ is prime power
2. incorporating complexity of modular operations.

# Answer
The dependence on the field is via the cost of arithmetic operations over the field. Since numbers in $\mathbb{F}\_q$ have bit size $O(\log q)$, the cost of each individual operation is polylogarithmic in $q$.
> 1 votes

---
Tags: algorithms, time-complexity, matrices, linear-algebra, decomposition
---


# Question
Title: Determining if $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} is not a regular language using Pumping Lemma?
In short, is this similar to how $a^nb^n$ is not a regular langauge?

$L$ = {$ { a^nsb^n : s \in L(a^\*b^\*) ,\ n \ge 1 } $}

For instance, if we have the string $w=a^psb^p$, and we know that $|xy| \le p$, there would simply be a disproportianate amount of a's or b's regardless of where we put $y$ ?

# Answer
> 1 votes
Your language is equal to $L(a^+b^+)$ (why?).

# Answer
> 1 votes
You cant use the pumping lemma to show that a language is regular, you can only show that if the lemma fails, then it is not regular. As an aside, the language you gave is regular, and as Yuval has said it is $L(a^+b^+)$, another way to look at $L(a^+b^+)$ is $L(a^1a^\*b^\*b^1)$ a DFA is the easiest way to show this one.

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


# Question
Title: In Coq, what does it mean to have an inductive type where the right-hand side of ":" is Prop?
I'm new to Coq, and my (rather limited) understanding is that inductive types are like algebraic datatypes in Haskell, so there is a constructor `data T = A a` with some arguments, and the result `A a` is a `T`: specifically a `T`, so I understand stuff like this:

```
Inductive List := Nil : List | Cons : nat -> List -> List.

```

where you apply a constructor and get a List, which defines what Lists (as opposed to something else) are.

So how exactly does it work that I can define an inductive type like this:

```
Inductive Person := Name : nat -> Person.
Inductive Knight : Person -> Prop := Knight_ : ∀(A:Person), Knight A.
Inductive Knave : Person -> Prop := Knave_ : ∀A, Knave A.

```

where the inductive type has Prop (or `Person -> Prop`?) on the right-hand side of it? This is supposed to represent "A is a knight" and "A is a knave" in knights-and-knaves puzzles. I think this is a way to encode the idea, but this is a little confusing, and I couldn't find an explanation of this. Some places in fact introduce inductive types as being similar to Haskell's data, but that's clearly not all of it.

# Answer
> 9 votes
Inductive types *are* similar to Haskell's `data`, but they are more general.

An inductive definition in `Set` describes a way to build a piece of data from smaller pieces. For example, the following definition defines a type called `prod` which allows taking two pieces of data and bundling them together.

```
Inductive prod (A B : Set) : Set :=  pair : A -> B -> prod A B.

```

(This definition exists in the standard library — with `Type` rather than `Set`, but I won't get into that distinction in my answer.) In English, given two data types `A` and `B`, and given a value `a` of type `A` and a value `b` of type `B`, I can build the value `pair a b` which has the type `prod A B`. (In the standard library, there's syntactic sugar for this: `(a, b) : A * B`.) And this is the only way to build a value of the type `prod A B`: given a value of this type, I can extract the two values that make it up (the primitive syntax for that is pattern matching, both in Haskell and in Coq).

You could take the same definition, but with `A` and `B` in `Prop`, and construct a type in `Prop`.

```
Inductive pprod (A B : Prop) : Prop :=  ppair : A -> B -> pprod A B.

```

What does this mean? Let's go through the English explanation above, applying the Curry-Howard correspondence: types become propositions, and values become proofs. So, given two propositions `A` and `B`, and given a proof `a` of the proposition `A` and a proof `b` of the proposition `B`, I can build a proof `ppair a b` which has the type `pprod A B`. And this is the only way to build a proof of `pprod A B`.

To build a proof of `pprod A B`, I need a proof of `A` and a proof of `B`. In other words, `pprod A B` is true if `A` and `B` are both true. There's a name for that: it's the conjunction of the two propositions — `pprod A B` is “A and B”.

Well, in the standard library, there's syntactic sugar for this: `pprod` is called `and` — the definition is

```
Inductive and (A B : Prop) : Prop :=  conj : A -> B -> and A B.

```

and there's syntactic sugar for `and A B` which is `A /\ B`.

This is pretty typical of how Coq works. In Coq, to say that something is true is to hold a proof of it. Coq implements a constructive logic, and makes that logic apparent. Every time you prove something, Coq builds the proof object and verifies that it's well-formed. It's rare to write down constructions in `Prop`, you'd usually let a tactic do it for you, but the objects always exist under the hood. (End a proof with `Defined.` instead of `Qed.` and run `Print mytheorem` to see the proof object for `mytheorem`. It can get big, but it's sometimes instructive to look at that for small proofs.)

I think it's instructive to look at how basic logical operators such as `and`, `or`, `not` and `exists` are defined (`forall` is a primitive concept). They're in the `Logic` library. It might not all make sense at first read, so revisit it again after you've practiced a bit.

To say that “P is true” in Coq, you build a proof of X. To show that “(A and B) is true”, you build a proof of (A and B), and you do this by building a proof of A and a proof of B. Likewise, to show that “(A or B) is true”, you build a proof of (A or B) by either building a proof of A or a proof of B (your choice, and if the proof depends on some variable, then you can pick a different side to prove depending on the value of that variable). This illustrates the relationship between constructivity and intuitionistic logic: the only way to prove `A \/ B` (syntactic sugar for `or A B`) is to either prove `A` or prove `B`, and this goes even when `B` is `not A`. If you can't manage to prove `A` and you can't manage to prove `not A` either, then you can't prove `A \/ not A`. The law of excluded middle does not hold. (It can be added as an axiom, but at a cost — you lose some of the advantage of constructivity.)

I don't think your definitions of `Knight` and `Knave` are particularly useful. You can prove `Knight p` and `Knave p` for any person `p`. The point of defining things in `Prop` is that they're not always true. Parametrized types in `Set` are often non-empty for every value of the parameters, but parametrized types in `Prop` are usually empty for some parameters — the parameters that make the proposition false.

---
Tags: coq, inductive-datatypes
---


# Question
Title: How is $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} a regular language?
My understanding is that a machine with finite states cannot keep track of the n's being the same in $L$ = {$ { a^nsb^n : s \in L(a^\*b^\*) ,\ n \ge 1 } $}, similar to the case with how $a^nb^n$ is not a regular language. For instance, if we take a string $aaaa ab bb$, where the fifth a and the following b are $s$, how is this valid? We have a disproportionate amount of a's to b's. Using the pumping lemma, I feel that this is disproven easily if $y$ (from $xyz$ division) is any number of a's at the beginning.

If this can be proven using a DFA, what is it?

# Answer
> 1 votes
You don't need to "keep track of $n$ being the same." Another way to write the language is

$$L = \\{a^na^ib^jb^n\mid n\geq 1,\ i,j\geq 0\\}=\\{a^{n+i}b^{j+n}\mid n\geq 1,\ i,j\geq 0\\}\\,.$$

So, now, given a string $a^sb^t$, you just need to decide if you can choose $n\geq1$ and $i,j\geq 0$ such that $s=n+i$ and $t=n+j$. If so, then $a^sb^t\in L$; otherwise, $a^sb^t\notin L$. If $s=0$ or $t=0$, we can't choose $n$, $i$ and $j$ as required, since $n\geq 1$. However, as long as $s\>0$ and $t\>0$, we can take $n=1$, $i=s-1$ and $j=t-1$. Therefore,

$$L = \\{a^sb^t\mid s,t\geq 1\\}\\,,$$

which is the language matched by the regular expression $aa^\*b^\*b$.

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


# Question
Title: Do we have knowledge bases only because the logics are not automated enough?
Do we have knowledge bases only because the logics are not automated enough? I.e. - is it true, that the ideal situation would be that we use the set of logical formulas as the knowledge base together with the deduction services of the relevant logic as the reasoning services for this "knowledge base". But not all the logics are automated enough and that is why we are seeking approximations and representation and reasoning services for the more restricted deductive systems.

# Answer
> 7 votes
Most logical systems in use are automated enough in principle. That is, there are algorithms which find the proof of a statement, if such a proof exists. The problem is *computational complexity*. Such algorithms are very, very, very, very, very slow. We only know efficient algorithms for special, easy cases.

More generally, knowledge representation is not just about logical deduction. You cannot logically deduce the fact that after Monday comes Tuesday and that tigers have legs, that is something that the machine has to be told, and it has to then store such knowledge. *How* do we store knowledge? That is a question of *expressivity* of the symbolic representation (the thing you call "logic"), and it is an issue that is largely separate logical deduction.

# Answer
> 0 votes
This is really better suited for philosophy stack exchange, but there are some questions that don't have deductive answers. When there is no deductively derivable fact of the matter as to a question, then logic and axioms can't help you. In these situations we often use inductive reasoning, tradition, or intuition. Examples include "where should I look first for my lost sock," "what axioms of mathematics should we use," and "is Bob likely to be lying to me when he says he didn't eat my cookie." Also many legal and moral quandaries may fall into this category, depending on the moral or legal system.

---
Tags: logic, knowledge-representation, reasoning
---


# Question
Title: Practicality of compressing data with hashing algorithms
I want to compress the string **0cc175b9c0f1b6a831c399e269772661**. I can do so by storing the string **a**, and, when decompressing, using **a** as input for the **MD5** hash algorithm to get the original string.

I realize it's impossible to represent $2^{128}$ possible strings with inputs less than 128 bits long, even if **MD5** had no collisions. However, a percentage of 128 bit strings could still be compressed using this concept.

Maybe another hash algorithm could be made with this application in mind. It does not need to be secure, irreversible, or computationally difficult. It just needs to represent the largest number of output strings given a string who's length is smaller than the output.

Multiple hashing algorithms could be used to increase the number of possible strings that could be compressed.

Is this idea practical? Could this idea be applied to compress large chunks of arbitrary data such as a file?

# Answer
> 2 votes
This idea is not practical, because there are some serious problems:

* You have to calculate all interesting hashes (less than hash length, here 128 bits), which is infeasible.
* There must be a way to tell apart compressed and not compressed strings, so some kind of terminator or escape sequence must be introduced.
* Since hash functions are designed with avalanche effect (small change in the input should yield huge difference in the output) there are no shortcuts for computations.
* The preimage resistance prevents from fast reversing, given hash calculate the input, this also gives another problem, once the data is compressed, the decompression also requires full hash -\> input mapping.
* The hash signature is quite specific, there are almost none naturally occuring natural texts with such substrings.
* If you want to use them in cascade it will be greedy approach, optimal one would require to calculate all cases to given depth and choose the smallest
* Multiple hashing algorithms enhance the additional description sequence, now the simple one bit (compressed or not) is not enough, it should also encode which algorithm was used.
* With collisions, the number of available hashes of given length decreases. The guarantee of better hash increases the complexity (both time and code).

The idea itself may be tempting, but it is not practical enough to be used in the common compression software, this tells quite a lot.

Please see also Compression with PRNG and Collision free hashes to compress and the compression of random data

---
Tags: information-theory, data-compression, hashing
---


# Question
Title: How to prove this language is not regular (via Fooling Set)
By using this fooling set, I am able to prove that the concatenation of *bz* is in the language *L*, but I still need to prove that *az* is not in the language to complete the proof.

This is also the point that the ceiling function is very tricky to deal with. It is also where I am lost.

Any hints and suggestions will be appreciated!

# Answer
> 0 votes
Let $s\_1 \< s\_2 \< \cdots$ be a subset of $\mathbb{N}$ with the following property:

$$ \limsup\_{n\to\infty} s\_{n+1}-s\_n = \infty. $$

I will show that the language $L = \\{ 0^{s\_n} : n \geq 0 \\}$ isn't regular using the fooling set method.

The first step is to find indices $i\_1 \< i\_2 \< \cdots$ such that $$ s\_{i\_1+1}-s\_{i\_1} \< s\_{i\_2+1}-s\_{i\_2} \< \cdots. $$ This can easily be done using the given property.

Our fooling set is $\\{ 0^{s\_{i\_n}} : n \geq 0 \\}$. To show that this is a fooling set, let $j \< k$, and consider the words $x = 0^{s\_{i\_j}}$ and $y = 0^{s\_{i\_k}}$. Let $z = 0^{s\_{i\_j+1}-s\_{i\_j}}$. Then $xz = 0^{s\_{i\_j+1}} \in L$ but $yz = 0^{s\_{i\_k}+s\_{i\_j+1}-s\_{i\_j}} \notin L$ since by construction, $$ s\_{i\_k} \< s\_{i\_k}+s\_{i\_j+1}-s\_{i\_j} \< s\_{i\_k+1}. $$

---

More generally, a unary language $\\{0^s : s \in S\\}$ is regular if and only if there exist $N,M$ such that $n \in S$ iff $n+M \in S$ for all $n \geq N$. There are many ways to show it, the most elementary being that a graph of unary DFA consists of a path leading to a cycle. This result implies yours.

---
Tags: formal-languages, regular-languages, check-my-answer
---


# Question
Title: Show that for A and B, a language J exists such that A $\leq_T$ J, B $\leq_T$ J
I am working on theory of computation problems, and I came across this one:

Show that for A and B, a language J exists such that $A \leq\_T J$, $B \leq\_T J$

The only $J$ I can think of for the moment is the language that uses a $TM$ $N$ which contains a recognizer $M1$ for $A$, and another recognizer $M2$ for $B$. $N$ uses oracle $J$ to check if input $x\in A U B$. If $J$ accepts, then it means that either $M1$ or $M2$ will halt, so $N$ can now simultate $M1$ and $M2$ simultaneously.

But I think there should be a simpler way to solve this..... any help?

# Answer
> 2 votes
Just define $J$ as $A\oplus B = \\{m \mid m =2k \text{ if } k \in A, \text{ and } m =2k+1 \text{ if } k \in B \\}$. Then $k \in A$ is decided by querying $2k \in A\oplus B$, and $k \in B$ is decided by querying $2k+1 \in A\oplus B$. Thus $A \leq\_T A\oplus B$, $B \leq\_T A\oplus B$.

This result is well known in the theory of computability. It establishes the least upper bound on the lattice of the Turing degrees of $A$ and $B$.

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


# Question
Title: Separating two strings without a separating character
Say you need to write a function such that you have string a and string b. The function argument is a concatenation of string a and string b. The function prints string a and string b separately. I'll explain.

For example one can think of a naive solution such that 'x' will be a separator character and so if we want to print "hello world" for example we create a function that prints everything as string a until it encounters an 'x' char and than it knows that string b is starting. So our argument will be something like:

void separateString("helloxworld");

But this eliminates the option of using 'x' as a char in our String.

I am sure that there is a simple solution to this that I am not getting.

Not looking for code, just your idea. The code will be easy to implement.

Thanks

# Answer
Just an extended note for the "quoting" techniques:

You can also pick one character of the alphabet (e.g. $a$) and interpret it as a space and use $aa$ for $a$:

```
 hello world  -> helloaworld
 amazing spacing -> aamaazingaspaacing

```

However it is easy to see that this approach can lead to ambiguities:

```
 a are doubled -> aaaaare doubled
                 --OK_DECODING   -> a are doubled
                 --WRONG_DECODING-> aa re doubled

```

These ambiguities can be avoided/ignored if we assume that the "special" character $a$ appears only in a well defined format and context.

Indeed this technique is still used for representing quotes or double quotes in well-known formats: e.g it is used for strings in the CSV format: every string is double quoted and the double quotes in a string are "doubled".

```
 COLUMN 1 | COLUMN 2            | COLUMN 3
 42        | My name is "Nobody" | He said "To be or not to be"
 43        | "Quote me"          | Charater " embedded

```

Are represented in CVS files as:

```
 42,"My name is ""Nobody""","He said ""To be or not to be"""
 43,"""Quote me""","Character "" embedded"

```

It is also used for single quotes in the SQL language:

```
 SELECT 'This is a quoted string: ''Hello world''!!!'

```

But more modern languages/formats usually prefer the escape technique (see Yuval's answer)
> 3 votes

# Answer
The simplest approach is to use *escape characters*. Suppose that you want `x` to be your separator. To escape it, you use `\x` (that would mean `x`). To escape `\`, you use `\\` (that would mean `\`).
> 2 votes

---
Tags: data-structures, strings
---


# Question
Title: Gale Shapley - Everyone ends up with second choice of partner
So I was asked to prove (or not) whether, in gale shapley algorithm, everyone can end up married to their second partner of choice or not. I think not but then I am not able to come up with a proof.

Thanks! :)

# Answer
Let us number the men $1,2,3,4$ and the women $a,b,c,d$ (the men propose to the women), with the following preferences: $$ \begin{align\*} &1\colon b \succ c \succ d \succ a & a\colon 1 \succ 2 \succ 3 \succ 4 \\ &2\colon b \succ a \succ d \succ c & b\colon 3 \succ 4 \succ 1 \succ 2 \\ &3\colon a \succ d \succ c \succ b & c\colon 2 \succ 1 \succ 4 \succ 3 \\ &4\colon a \succ b \succ c \succ d & d\colon 4 \succ 3 \succ 2 \succ 1 \end{align\*} $$ Let us trace the Gale-Shapley algorithm:

* Round 1M: $1,2$ propose to $b$; $3,4$ propose to $a$.
* Round 1W: $b$ accepts $1$; $a$ accepts $3$.
* Round 2M: $2$ proposes to $a$; $4$ proposes to $b$.
* Round 2W: $a$ accepts $2$, throwing $3$; $b$ accepts $4$, throwing $1$.
* Round 3M: $3$ proposes to $d$; $1$ proposes to $c$.
* Round 3W: $d$ accepts $3$; $c$ accepts $1$.

In the end, everyone is married to their second choice.
> 1 votes

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


# Question
Title: An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number
Suppose there is an unlimited number of pipes, each has length $x$ meters. There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given.

For example we need to have $n\_1$ pipes of length $x\_1$,$n\_2$ pipes of length $x\_2$,..., $n\_k$ pipes of length $x\_k$ $\forall i, x\_i \leq x$.

We need to cut the pipes of length $x$ such that the requirements to be fulfilled and also minimize the number of the used pipes.

For example for $x = 12$ and $$item1: x\_1=3,n\_1=50$$ $$item2: x\_2=5,n\_2=30$$ $$item3: x\_3=7,n\_3=80$$$$item4: x\_4=2,n\_4=90$$$$item5: x\_5=9,n\_5=15$$

we can cut the pipes in multiple ways. The worst solution is to allocate one pipe for each requirement, in this way the number of used pipes will be $$\sum\_{i=1}^{i=k}{n\_i} = 265$$

But by combining `item2` and `item3` into one pipe, we can reduce $256$ by $30$. In this way `item2` is prepared then we can combine `item1`, `item3` and `item4` to prepare the items and use the minimum number of the pipes.

As another solution we can also combine `item5` and `item1`, or even allocate one pipe of length $12$ for $4$ pipes of `item1`

**I would like to know is this a famous problem? and is there any efficient algorithm for it?**

# My Solutions

## Solution 1

Because I really don't know what the class of this problem is, I tried to solve this problem using the approximation algorithm given for the *Set Cover* problem.

The *item*s form the set of elements, and any combination of *item*s where the summation of their $x\_i$ is less than or equal to $x$ is a valid set and its cost equals to $$cost(set\_i) = x-\sum\_{item\_j \in set\_i}{x\_j} $$

But in set cover problem an element may appear in multiple sets while in this problem such thing is not reasonable. Besides that the $n\_i$s are different that is why the Set Cover solution is not working here.

## Solution 2

My second solution is a simple greedy algorithm. First I create set of valid sets as explained in the **Solution 1**, select the one with minimum `cost`. In this way at least one `item` with the minimum $n\_i$ is produced.

In the second step, first I need to update $n\_i$s (because some items are produced in the previous step) and remove the completely covered item from the list. If $set\_j$ was the set with minimum cost, Then there will be a few pipes with the length $$wasted= x - \sum\_{item\_k \in set\_j}{x\_k}$$.

For the remaining items in the list, if there is anyway to form elements in a set such that sum of their $x\_i$ is less than or equal to $wasted$ then we produce those pipes, else we should repeat from the first step with the new list.

# Answer
> 0 votes
Take a look to knapsack problem.

Simple algorithm (not the optimal solution)

1. order the item descending
2. cut the n5/(x\x5) ("\\" is integer division, i.e. 12\9=1) = 15 pipes to satisfy x5 = 9m and partially x1

Repeat step 2 for x3 = 7m and so on.

---
Tags: algorithms, optimization, greedy-algorithms
---


# Question
Title: Protocols for "almost equality" with one-sided error
In the well-known communication task *EQUALITY*, Alice has a string $x$ of $n$ bits, Bob has a string $y$ of $n$ bits, and their task is to determine whether $x = y$. In the public coin model, there is a probabilistic protocol which uses 2 bits, is always correct when $x = y$, and is correct with constant probability when $x \neq y$ (in fact, with probability 1/2).

The following generalization came up in a recent question. In the task *$k$-HAMMING* (where $k$ is a *constant* parameter), Alice and Bob hold strings $x,y$ of length $n$ bits, and their task is to determine whether the Hamming distance between $x$ and $y$ is at most $k$. *EQUALITY* is the case $k=0$.

When $k = 1$, we have the following nice protocol, which uses 5 bits, is always correct in the Yes case, and is wrong in the No case with probability at most 5/8. Alice and Bob agree on two random strings $z,w \in GF(3)^n$. Alice and Bob each compute the inner product of $z,w$ with their input, and compare the values. If both are equal or both are different, they output Yes, and otherwise they output No.

If the Hamming distance between $x$ and $y$ is $d$ then the probability $p\_d$ that $\langle z,x-y \rangle = 0$ is $1/3 + (2/3)(-1/2)^d$. We have $p\_0 = 1$, $p\_1 = 0$, and $1/4 \leq p\_d \leq 1/2$ for $d \geq 2$. This shows that the error probability when $d \geq 2$ is at most $p\_d^2 + (1-p\_d)^2 \leq (1/4)^2 + (3/4)^2 = 5/8$.

When $k \> 1$, a similar protocol works since using enough samples we can estimate $p\_d$ to any required accuracy. However, the resulting protocol no longer has one-sided error. One-sidedness can be recovered in many ways at the cost of using $O(\log n)$ bits of communication.

> Is there a one-sided error protocol for *$k$-HAMMING* for $k \geq 2$ using $O(1)$ communication?

# Answer
Here is a protocol with one-sided error for the case $k=2$.

Suppose we have $x,y \in \\{0,1\\}^n$.

1. Sample $N$ strings $z\_1,\dots,z\_N$ uniformly at random from $\\{1,4\\}^n$.
2. Alice sends $\alpha\_j = \sum\_i x\_i z\_{j,i} \bmod 5$ to Bob, and Bob sends $\beta\_j = \sum\_i y\_i z\_{j,i} \bmod 5$ to Alice.
3. Both parties compute $\gamma\_j = \alpha\_j - \beta\_j \bmod 5$. Let $\Gamma$ denote the set $\\{\gamma\_1,\dots,\gamma\_N\\}$ (suppressing duplicates, since it is a set).
4. If $\Gamma = \\{0\\}$ or $\Gamma \subseteq \\{1,4\\}$ or $\Gamma \subseteq \\{0,2,3\\}$, output "the Hamming distance is probably at most 2" (in fact, we can even say that the Hamming distance is probably 0, 1, or 2, respectively, depending on which case you are in). Otherwise, output "the Hamming distance is definitely at least 3".

Why does this work? If the Hamming distance is zero, then the only possible value for each $\gamma\_j$ is 0; if the Hamming distance is 1, the only possible values are 1,4; if the Hamming distance is 2, the only possible values are 0,2,3; if the Hamming distance is 3, the only possible values are 1,2,3,4; if the Hamming distance is 4 or greater, all values are possible.

Therefore, if the algorithm says "definitely at least 3", it will never be wrong.

Moreover, if the Hamming distance is 3 or greater, the probability of each possible value for $\gamma\_j$ is at least $1/8$. Consequently, by a union bound, the probability of wrongly outputting "probably at most 2" is at most $2(1 - 2/8)^N$, which can be made exponentially small by making $N$ sufficiently large. In particular, it suffices to take $N$ to be a small constant (e.g., $N=5$) to achieve a one-sided error, with a one-sided error probability less than $1/2$.

I haven't thought about whether this can be generalized to arbitrary $k$.
> 1 votes

# Answer
Here are two solutions. In both cases, the inputs are $x,y \in \\{0,1\\}^n$, and we are interested in checking whether the Hamming distance between $x$ and $y$ is at most $k$ or not.

**Solution 1 (D.W.):**

The two parties decide on a random string $z \in \mathbb{Z}\_{2k+3}^n$, compute $\alpha = \langle x,z \rangle$ and $\beta = \langle y,z \rangle$, and accept if $\alpha - \beta \notin \\{k+1,k+2\\}$.

If the Hamming distance between $x$ and $y$ is $d$, then $\alpha - \beta$ is distributed as the sum of $d$ many $\pm 1$ random values. When $d \leq k$, clearly $\alpha - \beta \notin \\{k+1,k+2\\}$. Conversely, when $d \> k$, the probability that $\alpha - \beta \in \\{k+1,k+2\\}$ is $\Omega(2^{-k})$.

**Solution 2 (Sa'ar Zehavi):**

The two parties decide on a random partition of $\\{1,\ldots,n\\}$ into $k+1$ parts, and run the one-bit equality protocol on each of them. They accept if the equality protocol succeeds (declares "equal") on at least one of them.

If the Hamming distance between $x$ and $y$ is at most $k$, then clearly the parties always accept. Otherwise, with probability $\Omega(e^{-k})$ all the $k+1$ parts will be different, and so the equality protocol will fail on all of them with probability $\Omega(2^{-k})$.
> 2 votes

---
Tags: communication-complexity
---


# Question
Title: Can we make a PDA with only 1 state which accepts a^n and n is odd?
We can have acceptance with empty stack, but in that case our stack at the start has to have a A in it, otherwise this machine will accept the empty string which is wrong

But can we have a non empty stack at the start? is my method right?

# Answer
> But can we have a non empty stack at the start?

By the formal definition PDA has the initial stack symbol $Z$ with which a computation starts.

The idea is to use three stack symbols $Z, Z\_{even}, Z\_{odd}$ to keep track of whether the number of $a$s read so far is even or odd. If the PDA reaches the end of string and topmost symbol is $Z\_{odd}$ then empty the stack.
> 2 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Comparing the Speed of Random Number Generation to Reading Data
Imagine you need $n$ random numbers from a Gaussian distribution with $\mu=0$ and $\sigma=1$. And you need to use each of these $n$ numbers $k$ times in various operations. Let's identify the numbers by $j \in 1 \ldots n$.

I see 3 methods of accessing these $n$ numbers during the operations:

1. Generate $n$ numbers once, store them in memory and read each one $k$ times.
2. Generate $n$ numbers once, store them on disk and read each one $k$ times.
3. Set the generator's seed to $j$ and generate the number $n * k$ times.

To determine the total run time, let's define the following terms:

* $T\_{rand}$: the time to generate 1 random number
* $T\_{seed}$: the time to set the seed
* $T\_{w,mem}$: the time to store 1 number in memory
* $T\_{w,dis}$: the time to store 1 number on disk
* $T\_{s,mem}$: the time to search 1 number in memory
* $T\_{s,dis}$: the time to search 1 number on disk
* $T\_{r,mem}$: the time to read 1 number from memory
* $T\_{r,dis}$: the time to read 1 number from disk

I believe the total run time for the three methods are:

1. $T\_{total,1} = n * T\_{rand}+ n * T\_{w,mem} + n * k * T\_{s,mem} + n * k * T\_{r,mem}$
2. $T\_{total,2} = n * T\_{rand}+ n * T\_{w,dis} + n * k * T\_{s,dis} + n * k * T\_{r,dis}$
3. $T\_{total,3} = n * T\_{seed}+ n * k * T\_{rand}$

It would seem strangely coincidental to me if these three methods had similar speeds. I can imagine one of them vastly outperforms the others. This is were I would like some advice. If helpful, you may assume:

* Number $n$ is large; possible so large that storing $n$ values in memory is not possible.
* The randomness can be of low quality.
* Storing and reading from disk is done efficiently, e.g. with Hadoop.

My questions are:

* Do you see other methods to solve this problem?
* What other information do I need to determine which method is the fastest?
* Which aspects of the procedure will dominate in determining the total time it takes?
* Which method is the fastest? And, if possible, why?

# Answer
> 1 votes
The answer is completely computer-architecture and random-generator -dependent. All you can do is to benchmark the different approaches after making them concrete.

---
Tags: complexity-theory, random-number-generator, storage
---


# Question
Title: Why encoding of graph in adjacency matrix is $\Omega (\sqrt n)$?
in the textbook of CLRS, p.1062 he says the following:

> if we use "reasonable" encoding of a graph as its adjacency matrix, the number m of vertices in the graph is $\Omega (\sqrt n)$, where n = |$\langle G\rangle|$ is the length of the encoding of G.

I want to know why $\Omega (\sqrt n)$? I mean it is adjacency matrix which takes $m^2$ but I don't know how he calculates it, so I would like someone to explain to me how we get this time complexity?

Thank you!

# Answer
> 4 votes
An $m\times m$ adjacency matrix requires $m^2$ bits, and $m=\sqrt{n}$ is just the solution to $m^2 = |\langle G\rangle| = n$.

The point of the $\Omega$ is that a reasonable encoding doesn't have fewer than $\sqrt{n}$ vertices in a description of length $n$. For example "Write out the $k\times k$ adjacency matrix followed by $2^k$ zeroes" isn't "reasonable" and a string of length $n$ would encode a graph with only about $\log n$ vertices.

---
Tags: algorithms, graphs, encoding-scheme
---


# Question
Title: Difference between row-polymorpism and bounded polymorpishm?
I recently came across this blog post by Brian McKenna explaining row polymorphism. This seemed like a wonderful idea to me, but then I realized it smells an awful lot like bounded parametric polymorphism:

With row-polymorphism:

```
sum: {x: int, y: int | rho} -> int
function sum r = r.x + r.y

```

With bounded parametric polymorphism:

```
sum: forall a <: {x: int, y: int}. a -> int
function sum r = r.x + r.y

```

Can someone clarify the differences to polymorphism between these two approaches?

# Answer
> 3 votes
So, there are a few differences:

* In row polymorphism, you've bound $\rho$ to a name, so you can use it elsewhere. For example, `forall rho . rho -> {x : int | rho}` is expressible with row polymorphism, but not purely using bounded polymorphism. Likewise, you can even express field *deletion* this way: `forall rho .{x : int | rho} -> rho` is a perfectly valid row-polymorphic type, but subtyping doesn't really have a way of expressing this.

Because row polymorphism lets you add and delete fields this way, usually it works with a "stack" semantics, so that old fields are shadowed when new fields of the same name are added.
* Bounded subtyping uses, well, subtyping. So with row polymorphism, you can't give `x : {x : int, y : int}` as argument to a function of type `{x : int} ->int`. But most systems with bounded subtyping would have non-polymorphic subtyping too, that would allow this, since most systems have `{x : int} <: {x : int, y : int}`.

Bounded subtyping tends to be bit more precise and flexible, and the "stack" semantics of row polymorphism don't arise that much. But inference is much easier for row polymorphism, and can work in the absence of any type annotations (for example, in Elm), which usually isn't the case in the presence of subtyping.

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


# Question
Title: is this a Context free Language : $L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$
$L=\\{W\_1W\_2 \mid W\_1 \ne W\_2 \\: \text{and} \\: |W\_1|=|W\_2|\\}$

Alphabet = { a , b }\*

Considering L={WW} is not context free, shouldn't this be non context free as well? otherwise can you provide a machine or grammar which accepts this?

# Answer
This is a classical example of a context-free language whose complement is not context-free. It is context-free since every word in $w$ has the form $$ \Sigma^i a \Sigma^j \Sigma^i b \Sigma^j = \Sigma^i a \Sigma^i \Sigma^j b \Sigma^j $$ or the similar form with the locations of $a$ and $b$ switched.
> 0 votes

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


# Question
Title: Tips for understanding the Pumping Lemma for Context-Free Languages
I'm having a hard time wrapping the idea in my head. Can anyone explain this as different from Sipser's perspective?

(I saw one discussion in reddit but it's for regular languages) https://www.reddit.com/r/compsci/comments/1pnjrp/the\_pumping\_lemma/

# Answer
One way of looking at the pumping lemma is in terms of the *pumping game*, a two-player game parametrized by an infinite language $L$. The two players are the *Prover* and *Challenger*, and the game goes as follows:

1. Prover picks an integer $n$.
2. Challenger picks a word $w \in L$ of length at least $n$.
3. Prover chooses a decomposition $w = xyz$ such that $|xy| \leq n$ and $|y| \ge 1$.
4. Challenger chooses an integer $i$.
5. If $xy^iz \in L$ then Prover wins, otherwise Challenger wins.

The pumping lemma states that:

> If $L$ is regular then Prover has a winning strategy.

The pumping lemma is often used in the contrapositive:

> If Challenger has a winning strategy then $L$ is not regular.

---

Here is an example: we will show that Challenger has a winning strategy for the language $L = \\{a^nb^n : n \geq 0\\}$.

In response to Prover's choice of $n$, Challenger chooses the word $w = a^n b^n$. In response to Prover's choice of a decomposition $w = xyz$ such that $|xy| \leq n$ and $|y| \geq 1$, Challenger chooses $i=0$. Then $xy^iz = a^{n-|y|}b^n \notin L$, and so Challenger wins.
> 2 votes

# Answer
This is simply an application of a well-known correspondence between logic and games to the statement of pumping lemma.

First notice that for any statement of the form: $$ S = \exists a\_1 \ldotp \forall b\_1 \ldotp \exists a\_2 \ldotp \forall b\_2 \ldotp \ldots \exists a\_n \ldotp \forall b\_n \ldotp p(a\_1,b\_1,a\_2,b\_2,\ldots a\_n,b\_n) $$ Here, truth value of $p$ is a function of variables $a\_1,b\_2,\ldots,a\_n,b\_n$. There is a corresponding (two-player, zero-sum, extensive-form) game $G\_S$ where

* $\exists$-player wins when the statement $p$ is **true**
* $\forall$-player wins when the statement $p$ is **false**
* The players take alternating turns **instantiating** the value of variables in order of $a\_1, b\_1, \ldots ,a\_n,b\_n$ starting with the $\exists$-player.

The statement $S$ is:

* true exactly when $\exists$-player has a winning strategy
* false exactly when $\forall$-player has a winning strategy

For the explicit application of this translation for pumping lemma, please see Yuval Filmus's answer.
> 2 votes

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


title: Set theory and computer science

text:
# Question
Title: Set theory and computer science
It's said that in Zermelo–Fraenkel set theory (ZFC) one can develop all of mathematics. How about computer science?

Is it possible to define algorithms as a first step? More specifically, how to define "if x = 1 then y else z"? How about loops?

# Answer
It all depends what you consider "computer science."

For what I would call "classical computer science" i.e. the theory of Algorithms, Turing Machines, etc. it can all be modelled in set theory.

A Turing Machine is just a tuple (which can be modelled using sets): a set of states, a tape-alphabet set, a transition function, etc. All of these are set-theoretic constructs, and even with nondeterminism, we replace the transition function with a relation, which is again set theoretic.

Similarly, we can define the semantics of programming languages using sets. Usually this just boils down to a big-step or small-step operational semantics, which again, is just defining relations.

Where things get iffy is with the so-called "alternate foundations of mathematics". This includes things like:

They provide alternate sets of axioms from which mathematics can be built up. For example, the usually discard excluded middle and axiom of choice. Homotopy type theory, for example, introduces the Univalence Axiom.

These systems tend to be heavily oriented towards computation through the Curry-Howard Correspondence, so that a proof can "run" on a computer. So they don't quite fit into ZFC, but are generally considered part of computer science.
> 4 votes

---
Tags: algorithms, computation-models, mathematical-foundations
---