# Question
Title: Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?
I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate back with **only inserts** but one might have to go back to change heights (since only nodes on the path from insertion point to root node have possibly changed in height, so we need to make sure we update them).

However, I was trying to form some type of proof that we don't actually recurse to the root and actually perform rebalancing. The proof I sort of had was the following:

The only way to recurse back to fix a unbalanced node is if we have two violations due to an insertion. One at some point down the tree and another one higher up the tree. When we do an insert the node increased height which caused these two unbalances. For us to have to recurse back we need to make sure even after the rebalancing of the lowest node, that the height doesn't decrease due to the rebalancing. This is unfortunately unavoidable because for that to happen, we'd need to be in one of the cases of rebalancing where the node's height doesn't change. Since the height of a node always decreases in an insert, then we don't actually need to rebalance.

Why don't we need to rebalance? That is because the only time we need to rebalance and the height doesn't change is when the right child of the lowest violating node $x$ has two subtrees that are balanced. That is not possible to happen because for that to happen, you need two inserts to cause that unbalance, but a single insert would cause the imbalance already, so the second insert won't make the right child of $x$ have two balanced subtrees.

# Answer
> 3 votes
You may have to rebalance during insertions, that much is clear: inserting a sorted sequence of values would otherwise lead to a degenerate tree.

By looking at the setup graphics of the four types of rotation, you can easily see that the height of the affected subtree after the insertion is *the same* as before. Thus, no node outside of this subtree can be imbalanced.

Thus, we never need more than one rotation when inserting. We can stop moving up the tree after we've rotated once, and efficient (non-recursive) implementations do exactly that.

# Answer
> 1 votes
When you rebalance on an insert the resulting node height is equal to what it was before the insert so you don't need to propagate to the root to change node height after a single or double rotation, after the rotation rebalancing is complete and node heights are already correct further up because they didn't change.
Often recursive insert implementations just keep going to the root because they don't maintain a way to signal the rebalancing is complete. Non-recursive bottom-up AVL tree rebalancing will always break out of the loop and return after a single or double rotation.

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


# Question
Title: How to get O(Big-oh) notation for following Code
What i came up with is this 1) inner loop goes to 2n and at each. step it increments n/3 times threfore **2log n** times it will execute 2) outer goes to n incrementing by 1 threfore n times

Hence for each value of outer loop innner executes n\* 2log n times... Threfore O(n\*2logn)

Que 1) Is this correct

Que2) If it is Correct then how to derive θ(theta), average case.

Please help me here

# Answer
There are a number of serious misunderstandings in this post.

1. Assuming that this code takes a pair of starting values $x,n$ as an input, this code describes a function, $f(x,n)$. However, $f$ can be calculated exactly, and there's no reason to describe it in terms of big-O notation. Big-O notation is used to describe an upper bound on a value that you don't know the precise value of. If you're looking to describe the function this code expresses you should calculate it, not use big-O. This code gives the function $f(x,n)=x+6n$.
2. Even if we ignore 1, I’m having trouble with your calculation. Where did the $\log(n)$ come from? The inner loop executes 6 times, rather than $2\log(n)$ times. I can elaborate on this point if you wish, but you can easily verify this by hand with small numbers.
3. You cannot leave the $x$ out of an upper bound on the complexity of code if $x$ is a variable in the code that isn't constrained. You might describe this code as $O(x+n)$ but to describe it as $O(n)$ is wrong.
4. $\Theta$ does not mean the average case complexity. $g=\Theta(f)$ when $g=O(f)$ and $f=O(g)$. Again, you shouldn't describe this using $\Theta$ because we can simply calculate the value exactly.

Despite point $2$, your answer (once we've amended it to be $O(x+n\log(n))$ isn't really *wrong* (assuming we are caring about an upper bound). This is because it's an upper bound that's bigger than the best description. In this sense, the code is also $O(x+e^{e^n})$. It's just that describing it as such is probably not helpful.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Proving there exists an infinite number of Turing machines is a decidable problem
I have a Turing machine M and I have to answer the question are there infinitely many Turing machines that recognize L(M)? I also need to describe a Turing machine that solves this problem. My idea is to say that we can simply increase the number of states by adding a new unreachable state. Each time I add a new state, it's still considered a new TM and because they're unreachable, I can say that they still accept the same language.

The only problem I'm having is describing a TM that can solve the problem. I was thinking that if I create a new TM (let's call it N) that represents M, I could say that N just needs to modify the transition function to create an unreachable state and once it does that it can add an infinite number of unreachable states which means there exists an infinite number of TM's. My problem is that I'm not sure if this is all I have to do to prove this and if it is then is my TM N enough to solve the problem or does it need to do more than just modify the transition function? N has to be decidable so it can't just keep adding states or else it will go on forever.

# Answer
> 1 votes
Given $L(M)$, there are countably infinite number of Turing machines that accept this language. You already describe in your post how to generate these machines. Thus the problem

> are there infinitely many Turing machines that recognize L(M)

is decidable. The TM machine that decides it simply outputs $1$ (ACCEPTS) on any input $\langle M \rangle$.

Note that your TM $N$ does not need to construct all machines, it just needs to always response "YES" since for any $M$ indeed there exists infinite number of TMs accepting $L(M)$.

---
Tags: computability, turing-machines
---


# Question
Title: Firefly algorithm number of objective function calls
Reading an article (arXiv) about the Firefly optimization algorithm, it is stated that the objective function is called only once per firefly per iteration, but following both the pseudo-code in the article and some implementations I found online I do not understand why this is the case..

As I understand the following holds:

* The objective function is called whenever we want to update the light intensity $I\_i$ of firefly $i$
* In a given iteration and firefly $i$, for every firefly $j$, if $I\_j\>I\_i$ we move firefly $i$ and immediately re-calculate the intensity.

From this, if the fireflies' intensities are ordered as $1,2,3,\dots,n$, and the updated intensity increases by each movement are small (i.e. each movement will increase the intensity by at most 1), in one iteration the first firefly will move $n-1$ times, the second $n-2$ times,... each movement calling the objective function for a total of $n(n-1)/2$ calls. Where does the figure of $n$ objective calls per iteration comes form?

# Answer
It seems to me that you are correct. I haven’t read the whole algorithm carefully though. One alternative is that maybe they intend for the movement to be simultaneous, so that the firefly that’s currently being placed moves towards all the bright fireflies at once, then recalculates once for the new position?

But as is, it seems like the pseudo code for the algorithm and the description don’t line up.
> 2 votes

---
Tags: algorithms, optimization
---


title: Compute visible vertices of a polygon

text:
# Question
Title: Compute visible vertices of a polygon
Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the vertices of $P$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ is completely in the polygon $P$.

One can use the accepted answer here to compute visible vertices in $P$ from a point $p$ in $\mathcal{O}(n\log{}n)$.

My question is, does an algorithm exist to do it in $\mathcal{O}(n)$ time?

# Answer
Yes, there are more algorithms to do so in $\mathcal O(n)$. The first is dated back to ElGindy and Avis in 1981, Lee 1983 and Joe & Simpson in 1985. The visibility algorithms use stack (the first one three stacks, further only one) and process vertices in order they appear at boundary.

The visibility algorithms described in book *Art Gallery Theorems and Algorithms* by Joseph O'Rourke. The book is out of print, available online.

Also author wrote a paper the vertex-edge visibility graph of polygon with Ileana Streinu in 1996, which with Chazelle's linear time triangulation and slight modification (simply by adding two edges from given point) would solve the problem in linear time.
> 3 votes

---
Tags: algorithms, computational-geometry, polygons
---


# Question
Title: How do I solve this graph with Dijkstra's Algorithm?
I just drew this graph completely random:

I found the shortest path (marked in red) by simply checking everything. But the reason was to use Dijkstra's algorithm. But when I try I get stuck in a loop. Lake a look at my calculations:

How to read it is:

* Top Row: Wich node
* Section t: Total distance traveled
* From: Wich node did I come from
* The 10 over S and every other section can be read like this
    + To come from S to node 1, the complete path takes 10 time units

So, if you try to follow Dijkstra's algorithm you will get something like this: S-\>D-\>C-\>5-\>4-\>6-\>D-\>S-\>5-\>4-\>6-\>D-\>(and so on)

I get stuck in a loop. I understand that when I return to S I can reset the time to 0, witch make at least the first bit correct, S-\>5-\>4, but than it get stuck.

How are you supposed to solve a problem like this based on how the algorithm is formed? For me, it is obviously stupid to just go around this route, but for an algorithm it is not.

Thank you in advance!

# Answer
> 2 votes
Firstly, I suggest that you start off with a simple graph (5 nodes would do). I believe you are mixing Dijkstra with A\* search algorithm and are trying to perform A\* search (even without knowing it).

For Dijkstra:

1. Assign to each node a distance value. 0 for initial node and infinity for all other nodes (since they are not visited)
2. Set initial node as current. Mark other nodes as unvisited. Create a set of all unvisited nodes.
3. For the current node, consider all of its neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.
4. When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity, then the algorithm has finished.
6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

If you need more help on this method, let me know!

---
Tags: graphs
---


# Question
Title: Post Correspondence problem provable instance
Let the Post Correspondence problem with input

$$K = ((x\_1, y\_1), . . . ,(x\_n, y\_n)), x\_i, y\_i ∈ \Sigma^\*$$

for $$ i = 1, . . . , n $$

Find a concrete solution for the input

$$K = ((001,0), (01, 011),(01, 101),(10, 001))$$

The Post Correspondence problem is undecidable so it's really hard to find a concrete solution. I've tried brute forcing it but it gets frustrating after a few tries.

Is there a logical way to deduce that K **is** a solution, rather than finding a pattern that works?

# Answer
The smallest solution is

> 0110011010010010110011001101001101001001101001001011000100101101010010010100100100101100110001010011010010011000100101100010010100100101001010011000100101

generated by the string

> bdcddbabdcdcddcddbaddbacdaacdddbabaaacdcdabaddbadaacdaacaacabadaac

where $a = (001,0)$, $b=(01,011)$, $c=(01,101)$, $d=(10,001)$.

This solution can be found by a simple pruning procedure:

1. Start with the list $L$ which contains a pair of empty strings.
2. At each iteration, attempt to add each of the four "pieces" to each of the pairs in $L$, and remove any pair for which no string is a prefix of the other.

Eventually $L$ will contain a pair of equal strings, in this case after 66 iterations.

As an example, here is the contents of $L$ in the first few iterations:

1. Iteration 1: (001,0), (01,011)
2. Iteration 2: (001001,00), (0110,011001)
3. Iteration 3: (011001,011001011), (011001,011001101)
4. Iteration 4: (01100101,011001011011), (01100101,011001011101), (01100110,011001101001)

The number of pairs of strings at every iteration fluctuates but generally increases, and after 66 iterations reaches 12081, one of which is the solution given above.
> 1 votes

---
Tags: undecidability, decision-problem
---


# Question
Title: What are the rules for positive recursive types in dependent type theory?
I've recently started independently learning type theory, using a combination of papers found online and ncatlab.org (but have not worked with category theory), and am about to start reading TAPL.

I'm interested in understanding how recursive types can be substituted for inductive types in dependent type theory (we assume dependent sums, dependent products, identity types and finite types 0, 1, 2 in our background theory), however I am unable to find a definition for recursive types that doesn't use unrestricted fixpoint operators and hence lack strong normalisation.

I've attempted to do this myself, but the dependent eliminator seems slightly too weak, and a restriction on `if b then x else y` such that the boolean expression is evaluated before `x` and `y` can be reduced seems to be required for normalisation.

$$\frac{A:\text{Type} \vdash F(A):\text{Type} \\ A\text{ is positive in }F(A)}{\mu A.F(A):\text{Type}}$$

$$\frac{a:F(\mu A.F(A))}{S(A):\mu A.F(A)}$$

$$\frac{B:\text{Type}, b:B \vdash C(b,B):\text{Type} \\ B:\text{Type}, e: \prod\_{b:B}C(b,B))\vdash R(B,e) : \prod\_{f:F(B)}C(f,F(B))}{rec(R):\prod\_{a:\mu A.F(A)}C(a, \mu A.F(A))}$$

$$\frac{B:\text{Type}, b:B \vdash C(b,B):\text{Type} \quad a:\mu A.F(A)\\ B:\text{Type}, e: \prod\_{b:B}C(b,B))\vdash R(B,e) : \prod\_{f:F(B)}C(f,F(B))}{rec(R)S(a)=R(\mu A.F(A),rec(R))a:C(a, \mu A.F(A))}$$

Where `A` is positive in `F(A)` precisely when `A` does not occur in any type indexing any dependent product types in `F(A)`.

Is my formulation correct? What is the correct way to formulate rules for normalising recursive types, and are there any references that I could look at that expand on these?

# Answer
> 8 votes
### Why are recursive types seldomly seen in dependent type theory?

The point of inductive types is precisely that you get normalization. Unrestricted recursive types simply lead to non-normalizing terms.

Given any type $A$, we may inhabit $A$ with a non-normalizing term as follows. Consider the recursive type $$D = D \to A.$$ The term $\omega \mathrel{{:}{=}} \lambda d : D . d \\; d$ has type $D \to A$ and it also has type $D$, since they are equal. Therefore $\omega \\; \omega$ has type $A$, and in addition $\omega \\; \omega$ reduces to itself, giving a non-normalizing term.

If instead of $D = D \to A$ we have just $D \cong D \to A$ then an easy adaptation of the above argument leads to the same conclusion. You just have to coerce $d$ to have type $D \to A$.

Is this bad? If you're using type theory to write programs then it probably isn't that bad. It's actually kind of cool. But if you're using type theory to do reasoning, i.e., you want ot use types as propositions, then it's bad because every type has an inhabitant and so every propostion has a proof. It just depends on what you want from type theory.

### What are the rules for recursive types?

$\newcommand{\Type}{\mathsf{Type}}$ Let us try to formulate the rules for recursive types. A reasonable attempt goes along the same lines as what you've suggested: $$\frac{\Gamma, X : \Type \vdash F(X) : \Type}{\Gamma\vdash \mu X . F(X) : \Type}$$ $$\frac{\Gamma \vdash e : F(\mu X . F(X))}{\Gamma \vdash S(e) : \mu X . F(X)}$$ $$\frac{\Gamma, y : \mu X . F(X) \vdash C(y) : \Type \qquad \Gamma, x : F(\mu X . F(X)) \vdash f(x) : C(S(x)) \quad \Gamma \vdash u : \mu X . F(X) }{\Gamma \vdash \mathsf{rec}\_F(\[x . f(x)\], u) : C(u)}$$ We shouldn't forget to ask about equations that we expect to hold. The $\beta$-rule would be $$\mathsf{rec}\_F(\[x . f(x)\], S(e)) = f(e)$$ and let us throw in an $\eta$-rule $$S(\mathsf{rec}\_F(\[x . x\], u)) = u.$$ The $\eta$-rule says that if we take apart $u : \mu X . F(X)$ and put it back together, we will get $u$. So far we have a map $S : F(\mu X . F(X)) \to \mu X . F(X)$, but we also want $R : \mu X . F(X) \to F(\mu X . F(X))$ together with $$S(R(u)) = u \qquad\text{and}\qquad R(S(e)) = e \tag{1}$$ These say that $S$ and $R$ form an isomorphism between $F(\mu X . F(X))$ and $\mu X . F(X)$. We can get such an $R$, namely $$R \mathbin{{:}{=}} \lambda y : F(\mu X . F(X)) . \mathsf{rec}\_F(\[x . x\], y).$$ Indeed, we have by the $\beta$-rule $$R(S(e)) = \mathsf{rec}\_F(\[x . x\], S(e)) = e$$ and by the $\eta$-rule $$S(R(u)) = S(\mathsf{rec}\_F(\[x . x\], u) = u.$$

We could have started with having $S$ and $R$ satisfying equations (1), and that would allow us to *derive* the eliminator as $$\mathsf{rec}\_F (\[x . f(x)\], u) = f(R(u)).$$ Such an eliminator satisfies the $\beta$-rule and the $\eta$-rule, quite obviously. This should give us pause. We discovered that our rules say precisely that $\mu X . F(X)$ is isomorphic to $F(\mu X . F(X))$ *and nothing else*. This is not good, because the rules should fix the meaning of $\mu X . F(X)$ up to equivalence of types.

To see that the rules are no good, consider the case $F(X) = X$. *Every* type is a fixed point of $F$, and our rules say nothing about which one $\mu X . X$ should be. Indeed, we can take an arbitrary type $A$ and set $R$ and $S$ to be the identity maps. That will satisfy all the rules for $\mu X . X$.

We should somehow state *which* fixed point of $F$ we have in mind when we write down $\mu X . F(X)$. a reasonable choice would be to ask for the *smallest* or *initial* one. But what does that mean? In category theory it means that there is a unique homomorphism from the algebra $S : F(\mu X . F(X)) \to \mu X . F(X)$ to any other $F$-algebra. Here we rely on the fact that $F$ is a *functor* so that we can reasonably talk about $F$ applied to a map. But our $F$ is not going to be a functor in general because it might break covariance (try to extend $F(X) = X \to X$ so that it takes $f : A \to B$ to some $F(f) : F(A) \to F(B)$ and you will see what the problem is). We are stuck, as we have no good criterion for picking one of possible fixed points of $F$!

The way out is to decompose $F : \Type \to \Type$ according to covariant and contravariant arguments, $$F : \Type \times \Type^{\mathrm{op}} \to \Type.$$ For example $F(X) = X \to X$ becomes $F(X\_1, X\_2) = X\_2 \to X\_1$. But now it's not clear what a fixed point of $F$ might be. All this leads to Freyd's notion of *algebraically compact categories* and a beautiful theory surrounding them. The theory can be applied to categorical models of programming languages to explain how recursive types work there. When we throw in *dependent* types, then as far as I know, things break and nobody knows what to do. But I would love to be proved wrong!

The sort of recursive types we spoke about here goes under the name isorecursive types. The other option are equirecursive types, see the same link.

# Answer
> 2 votes
A pretty comprehensive reference is Peter Dybjer's Inductive Families paper that presents a very general class of inductive types (I've rarely seen them called "recursive types").

Note that positivity is subsumed by the condition: there exists a morphism

$$ \mathrm{map}:\Pi\_{T\ U:\mathrm{Type}} (T\rightarrow U)\rightarrow F\ T\rightarrow F\ U$$

and it's reasonable to ask that every such family define an inductive family. I believe this is the view taken by Ralph Matthes in Monotone Fixed-Point Types And Strong Normalization.

---
Tags: reference-request, type-theory, dependent-types, types-and-programming-languages
---


# Question
Title: Draw a function by only using two input NOR gates
T = (BD + A'BC'+A'CD)

How can i draw this by only using NOR-Gates? This is what i have done so far: https://i.stack.imgur.com/nIujl.jpg

Have I understood this right?

# Answer
Yes, looks like you understood the question correctly and are implementing only using NOR-gates.

I also see correct usage of DeMorgan's Theorem.

Your answer seems to be **correct**. Good luck!
> 0 votes

---
Tags: logic
---


# Question
Title: Is there a limit to data compression without mentioning Kolmogorov complexity?
I want to develop a previous answer to Is there a known maximum for how much a string of 0's and 1's can be compressed?.

I've looked at the Hutter Prize and various compression benchmarks. The compression records are graphed below over a 12 year period. The red curve is an exponential fit, which seems to be asymptotic to something much greater than zero (10MB?). The test file (enwik8) is a bulk extract from Wikipedia, and I don't think that Mr Kolmogorov can help us here.

I'm not overtly asking what the limit is. I'm just asking is there (or could there possibly be) a limit to data compression without Mr. Kolmogorov, whilst using contemporary science? Intuitively and as the fitted curve suggests, there must be some limit as the data can't be compressed to 1 bit. Can anyone expand on any research regarding how close we might be to a minimum value for losslessly compressing enwik8? Is another 25% improvement possible? Is there any active research in this field or is the Hutter team leading the world?

# Answer
For any fixed piece of data, you can create an encoding where that specific piece of data is encoded by 1 (or possibly zero) bits. So yes you can most definitely compress things down to 1 bit. This is, of course, silly. We want to know how the compression algorithm behaves on multiple pieces of data because we want to use the same algorithm (or the same shared piece of data) multiple times.

Any compression algorithm *must* be bigger on some inputs than the original data. In fact, if you consider every possible input there is no net compression but there might be a net increase in size. So if we look at everything compression isn't even possible. The trick is that some data is more probable than other data and we can design algorithms that are smaller in the probable case. So each individual algorithm only really has a "compression ratio" if you can give a probability distribution over the inputs, then you can say what the expected output size is or what the expected compression ratio is. If your probability distribution has maximum entropy you'll see an expected compression ratio of at least 1. Importantly the entropy of this distribution tells us how much we can compress this sort of data. You don't get to just throw it out; it always applies.

Shannon's source coding theorem tells us what the theoretical limits are for compression algorithms *not* just compression algorithms on streams of data of a particular sort. Say you have some data with some distribution then you can compute how "good" this compression algorithm is by sampling data and seeing what the compression ratio is on average. Well, this is the same thing as compressing one giant file that meets Shannon's source coding theorem's requirements! So the entropy of the data still tells us how much we can compress it on average.

If your data is such that it's the concatenation of a fixed number of independent fixed size samples then Huffman encoding is optimal no matter what distribution the fixed size samples come from. 1) these properties seldom hold in practice and 2) when they do the optimality will only kick in for very large data. For instance, say you sample a bunch of IEEE double precision floating point numbers from an approximation of a normal distribution. Huffman encoding is technically optimal in this case but you're unlikely to see the same data more than once unless your data set is huge. I think other compression algorithms are known to be optimal for different groups of distributions over data but you'll have to do some digging to find them; I am not aware of any others off the top of my head. So as long as your data has a certain known distribution that fits one of the cases we know the optimal algorithm for AND your data is sufficiently large (or the entropy of your distribution sufficiently low) so as to have this result even be meaningful.

Generally, we don't even know what the distribution of the data is! We can make statistical inferences based on the data we have but properly fitting a probability distribution is a hard problem. Without specifying a probability distribution we don't have a sensible way to specify how good a compression algorithm is. The quality of practical compression algorithms is basically just due to algorithm designers being good at guessing what sorts of distributions your data might be sampled from and also being good at fitting which specific distribution it was sampled from in cases where that makes sense. For instance, the gzip algorithm effectively wagers that your data will have repeated values in it (especially after some transformations are performed on it). This is clearly just a guess the designers made but it happens to be a damned good guess in practice. If you assume that your data is a stream of independently sampled symbols from the same distribution then you can fit the distribution and construct a Huffman encoding for the data; this has a lot of flaws in practice but it's a lot better than nothing in practice as well. There is no reason in general that that has to be true.

So is there a limit? Well given the only consistent notion of a "compression ratio" that I know of the answer is given by Shannon's source coding theorem.
> 5 votes

---
Tags: data-compression
---


# Question
Title: Dijkstra algorithm step in Introduction to Algorithms
In the introduction to algorithms proof of Dijkstra, I don't understand why the statement "both y and u were in V-S when u was chosen". We add x before y, and so we relax d\[y\] with the the edge $$\omega(\<x,y\>) + \delta(s,x)$$, d\[u\] can't be smaller than delta\[u\], so shouldn't y be in S when we add x to S? thanks.

# Answer
$u$ is supposed to be the first node to be insert in $V$ such that $d(s, u) \neq \delta(s, u)$. Before the insertion, $u$ is in $S-V$, it's clear. In addition, $y$ is supposed to be the first node in a choosen optimal path $s -\> u$ to belong to $S - V$ when picking $u$ from $S - V$. So before we insert $u$ in $V$, $u$ and $y$ are both in $S - V$. Note that $y$ can be equal to $u$.
> 0 votes

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


# Question
Title: If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible?
We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N\_c$ such that for all $n \> N\_c$, $$\epsilon(n)\<\frac{1}{n^c}$$ (From wikipedia)

Assume that two probabilistic polynomial-time algorithms $O\_{1},O\_{2}$ satisfy that $$ \Sigma\_{y \in \\{\\, 0,1 \\,\\}}\left\vert \mathrm{Pr}\left\[ O\_{1}(x) = y \right\] - \mathrm{Pr}\left\[ O\_{2}(x) = y \right\] \right\vert \leq \epsilon\_{1}(n) $$ for all $x$, where $\left\vert x \right\vert = n$ and $\epsilon\_{1}$ is negligible.

Let $A$ be a probabilistic polynomial-time algorithm. Can we get that $$ \Sigma\_{y \in \\{\\, 0,1 \\,\\}}\left\vert \mathrm{Pr}\left\[ A^{O\_{1}}(x) = y \right\] - \mathrm{Pr}\left\[ A^{O\_{2}}(x) = y \right\] \right\vert \leq \epsilon\_{2}(n) $$ for all $x$? Where $\left\vert x \right\vert = n$ and $\epsilon\_{2}$ is negligible.

# Answer
Given $x$, define $p\_1(x,y) = \Pr\[O\_1(x) = y\]$ and $p\_2(x,y) = \Pr\[O\_2(x) = y\]$. Let $$ \begin{align\*} \delta\_x &= \sum\_y \[\max(p\_1(x,y),p\_2(x,y)) - \min(p\_1(x,y),p\_2(x,y))\] \\ &= \sum\_y |p\_1(x,y) - p\_2(x,y)| \\ &\leq \epsilon\_1(n). \end{align\*} $$ On the other hand, $$ \sum\_y \[\max(p\_1(x,y),p\_2(x,y)) + \min(p\_1(x,y),p\_2(x,y))\] = \sum\_y \[p\_1(x,y) + p\_2(x,y)\] = 2. $$ Therefore $$ \sum\_y \min(p\_1(x,y),p\_2(x,y)) = 1 - \frac{\delta\_x}{2}. $$ Consider now the following random process that generates two random variables $R\_1,R\_2$:

* For every $y$, with probability $\min(p\_1(x,y),p\_2(x,y))$, generate $R\_1=R\_2=y$.
* Otherwise (this happens with probability $\delta\_x/2$):
    1. For every $y$, with probability $\frac{p\_1(x,y)-\min(p\_1(x,y),p\_2(x,y))}{\delta\_x/2}$ generate $R\_1=y$.
    2. For every $y$, with probability $\frac{p\_2(x,y)-\min(p\_1(x,y),p\_2(x,y))}{\delta\_x/2}$ generate $R\_2=y$.

This process is a coupling that generates two random variables $R\_1,R\_2$ with the following properties:

1. $R\_1 \sim O\_1(x)$.
2. $R\_2 \sim O\_2(x)$.
3. $\Pr\[R\_1 \neq R\_2\] = \delta\_x \leq \epsilon\_1(n)$.

---

Let us go back to your algorithm $A$, and suppose that it runs in time $T(n)$. Use the coupling above to generate two random variables $B\_1,B\_2$ with the following properties:

1. $B\_1 \sim A^{O\_1}(x)$.
2. $B\_2 \sim A^{O\_2}(x)$.
3. $\Pr\[B\_1 \neq B\_2\] \leq T(n) \epsilon\_1(n) =: \epsilon\_2(n)$.

Note that $\epsilon\_2(n)$ is negligible. We have

$$ \begin{align\*} &\sum\_y |\Pr\[A^{O\_1}(x) = y\] - \Pr\[A^{O\_2}(x) = y\]| \\ = &\sum\_y |\Pr\[B\_1 = y\] - \Pr\[B\_2 = y\]| \\ = &\Pr\[B\_1 \neq B\_2\] \sum\_y |\Pr\[B\_1=y|B\_1 \neq B\_2\] - \Pr\[B\_2=y|B\_1 \neq B\_2\]| \\ \leq &\Pr\[B\_1 \neq B\_2\] \sum\_y (\Pr\[B\_1=y|B\_1 \neq B\_2\] + \Pr\[B\_2=y|B\_1 \neq B\_2\]) \\ \leq &2\epsilon\_2(n), \end{align\*} $$ since given $\Pr\[B\_1=y|B\_1=B\_2\] = \Pr\[B\_2=y|B\_1=B\_2\]$.
> 1 votes

---
Tags: polynomial-time, probabilistic-algorithms, oracle-machines
---


# Question
Title: Prove that a DFA will transition to the same state after $\gcd(i,j)$ steps where $i$ and $j$ steps can be taken to reach that state
Suppose $M=(Q,\Sigma,\delta,q\_0,F)$ is a deterministic finite automaton, and suppose there exists a state $q \in Q$, a string $z \in \Sigma$, and integers $i,j\>0$ such that $\delta(q,z^i)=\delta(q,z^j)=q$. Prove that $\delta(q,z^{gcd(i,j)})=q$

I can intuitively say that starting from a state $q$ if you take $x$ steps on a DFA to reach the same state and at the same time $y$ steps also takes the DFA to the same state, then there exists a cycle that is repeated $\gcd(x,y)$ times to reach the same state again and again. Is this correct for a DFA? How can I prove this formally?

# Answer
> 0 votes
Consider the sequence $q(n) = \delta(q,z^n)$ for $n \geq 0$. Let $b$ be the smallest index so that $q(a) = q(b)$ for some $a \< b$. It is not hard to check that all further iterates cycle through the values $q(a),\ldots,q(b-1)$. Since we are given that $q(i) = q(0)$, it follows that $a = 0$, and so the function $\pi$ on $\\{q(0),\ldots,q(a-1)\\}$ defined by $\pi(q') = \delta(q',z)$ is a cyclic permutation.

We are given that $\pi^i(q) = \pi^j(q) = q$. Since $\pi$ is a permutation, also $\pi^{-i}(q) = \pi^{-j}(q) = q$. It follows that for any integer $\alpha,\beta$ (not necessarily non-negative) $\pi^{\alpha i + \beta j}(q) = q$. In particular, Bezout's identity shows that $\pi^{\operatorname{gcd}(i,j)}(q) = q$, and so $\delta(q,z^{\operatorname{gcd}(i,j)}) = q$.

---
Tags: finite-automata
---


# Question
Title: Is the difference between two regular expressions a new regular expression?
Let say the following:

Given `Ax` and `Bx` two literals which represent `POSIX` regular expressions.

Let def A as the set of literals that match `Ax`. The same def for B.

Using relative complement operation, is there always regular expression for $A/B$ set, for every pair of `Ax,Bx`?

I attach an example:

```
Ax := a.*
Bx := a.*b$
// The difference A/B would be
Cx := a.*[^b]$

```

# Answer
While regular languages are indeed closed under set difference, there is no nice way of effecting this operation on regular expressions. Indeed, even regular expression *complementation* can result in an exponential blow-up. One simple example is the regular expression $r\_n = \sum\_{i=1}^n (\sum\_{j \neq i} \sigma\_j)^\*$ over the alphabet $\Sigma = \\{\sigma\_1,\ldots,\sigma\_N\\}$, which corresponds to all words which do not have all letters of the alphabet. This regular expression has polynomial length (in $n$), but every regular expression for $\Sigma^\* \setminus L(r\_n)$ has exponential length.
> 4 votes

# Answer
Regular languages are closed under relative complement. Since regular expressions encode exactly the regular languages, you can always find a regular expression that matches the relative complement of two other regular expressions.
> 4 votes

---
Tags: regular-expressions
---


# Question
Title: Can the semantics of a numeric hierarchy be faithfully represented in Haskell?
I am trying to represent a fragment of a number hierarchy using the Haskell concepts of *value*, *type*, and *type class*. I would like the Haskell code to reflect the mathematical semantics $\vdash ((x \in \mathbb{N}) \land (\mathbb{N} \subset \mathbb{Z}\subset \mathbb{Q}) \Rightarrow (x \in \mathbb{Q}))$. In words, given that the set $\mathbb{N}$ of natural numbers is a subset of the the set $\mathbb{Z}$ of integers and integers are a subset of rationals $\mathbb{Q}$, we can deduce that every natural number is an rational number. I omit the constraint that natural numbers are actually a *proper subset* of integers.

Below is my attempt at relating the math and Haskell semantics. I am unsure whether a class is a set of types as stated by GAST (Section 3.5) and hence a type can be considered as an element of a class $(T \in TC)$.

Note it is possible that $V\_1=V\_2$ (e.g. 1:Nat=1:Int)

Below is my flawed attempt to capture the mathematical meaning using Haskell. I am aware that implementing rationals would lead to a situation where rationals were represented by both a type and a type class (not good!). Please note for research purposes I am restricted to only using values, types,and type class. I am not intentionally seeking to impose Object Oriented class semantic on Haskell.

```
data Natural = One | Suc Natural deriving Show
data Integers = Zero | Succ Integers deriving Show

class RationallNumbers x where
  plus::x -> x -> x

instance RationallNumbers Integers where
 plus  x  Zero = x
 plus  x  (Succ y)  = Succ (plus x  y)

instance RationallNumbers Natural where
 plus  x  One = Suc x
 plus  x  (Suc y)  = Suc (plus x  y)

twoPlusTwoNat = plus (Suc One)  (Suc One)
twoPlusTwoInt = plus (Succ (Succ Zero))  (Succ (Succ Zero))

```

To sum up my question is:

Can the numeric hierarchy described be represented in Haskell using the semantic concepts of values, types, and classes?

Related questions: A mathematical (categorical) description of type classes, Is there a model theory for Haskell type classes?

# Answer
> 2 votes
Yes, it is definitely possible. However your approach is a good starter but keep in mind to have a functional approach on writing code in Haskell. You can create expressions so you can define and 'override' methods.

As a suggestion I will give a part of code of how such expressions can look like as values and types.

```
data Exp = Lit Value
         | Assign Name Exp
         | Variable Name
         | Apply Exp Exp
         | Assist Name Exp
         | Exp :+:  Exp
         | Exp :-:  Exp
         | Exp :*:  Exp
         | Exp :=:  Exp
         | Exp :==: Exp
         | Exp :/=: Exp
         | Exp :>:  Exp
         | Exp :>=: Exp
         | Exp :<:  Exp
         | Exp :<=: Exp
         | Exp :&&: Exp
         | Exp :||: Exp
         deriving (Show)

```

This is some code out of a language I've written for controlling micro-controllers. The evaluation can be done as following:

```
-------------------------------------------------
-- Evaluate Expressions Utilities
-------------------------------------------------
-- Evaluate Integer Arithmetic operations
evalInt :: KDLMap -> Exp -> Int
evalInt _ (Lit n)          =  kdlintToInt n
evalInt k (Variable n)     =  kdlintToInt $ searchVariable' n k
evalInt k (e :+: f)        =  evalInt k e + evalInt k f
evalInt k (e :*: f)        =  evalInt k e * evalInt k f
evalInt k (e :-: f)        =  evalInt k e - evalInt k f
evalInt _ _                =  Prelude.error "Unable to perform operation."

-- Evaluate Boolean operations with Integers
evalIntBool :: KDLMap -> Exp -> Bool
evalIntBool k (e :<:   f)         =  evalInt k e <  evalInt k f
evalIntBool k (e :>:   f)         =  evalInt k e >  evalInt k f
evalIntBool k (e :<=:  f)         =  evalInt k e <= evalInt k f
evalIntBool k (e :>=:  f)         =  evalInt k e >= evalInt k f
evalIntBool k (e :/=:  f)         =  evalInt k e /= evalInt k f
evalIntBool k (e :==:  f)         =  evalInt k e == evalInt k f
evalIntBool _ _            =  Prelude.error "Unable to perform operation."

-- Evaluate Boolean operations with Booleans
evalBool :: KDLMap -> Exp -> Bool
evalBool _ (Lit n)         =  kdlboolToBool n
evalBool k (Variable n)    =  kdlboolToBool $ searchVariable' n k
evalBool k (e :&&: f)      =  evalBool k e && evalBool k f
evalBool k (e :||: f)      =  evalBool k e || evalBool k f
evalBool _  _              =  Prelude.error "Unable to perform operation."

```

For more information, hit me up. I will provide it on my github quite soon, so you can see more. But to answer your question, yes it's definitely possible.

---
Tags: programming-languages, number-theory, haskell
---


title: Complexity class NP and MA

text:
# Question
Title: Complexity class NP and MA
Is there any example of any natural problem which is known to be in MA, but not yet to known to be in NP?

I am aware that Graph Nonisomorphism (GNI) is known to be in AM which is considered a superset of MA. Can we construct a language (which may be non-natural) which is in MA, but not in NP?

# Answer
The same hardness assumption that implies P=BPP also implies NP=MA (at least according to the complexity zoo).

Even if the hardness assumption is wrong, separating NP from MA would be a huge achievement, since it would imply that P is different from NP (as MA is in the polynomial hierarchy).
> 3 votes

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


# Question
Title: $ACC^{0}$ vs Poly-size circuits of bounded degree
We know that NEXP $\not\subset ACC^0$ **(Ryan Williams'10 Result)**. Also, We know that even $\Sigma\_{2}^{P}$ cannot have polynomial circuits of bounded degree i.e. $SIZE(n^k)$ for some $k \in N$ **(Kannan's Result)**. Does this give a hint towards $ACC^0$ is far more powerful than polynomial circuits of bounded degree? Are they even comparable?

# Answer
$ACC^0$ and $SIZE(n^k)$ are probably incomparable for all $k$.

$ACC^0$ is conjectured not to contain $Maj(x\_1,..,x\_n)$, which has linear size circuits (think about the naive Turing machine for majority and transform it into a circuit, things are much easier when you don't have a depth restriction). This shows that it probably holds that $SIZE(n)\not\subseteq ACC^0$.

On the other hand, $ACC^0$ does allow you to use polynomially many gates (with no degree restriction). We will show that under a certain assumption, for every $k\in\mathbb{N}$ it holds that $ACC^0\not\subseteq SIZE(n^k)$. Consider the problem of deciding whether a graph contains a $c$-size clique (where $c$ is a constant independent of the input).

This problem is obviously in $AC^0$ (for all $c\in\mathbb{N}$), since you can, in the first level, link all subsets of $c$ vertices into AND gates to check whether they form a clique, and in the second level link all the results from the previous level into an OR gate.

If this can be done using $SIZE(n^k)$ circuits, then $\mathsf{NP\subseteq P/Poly}$, since we can construct polynomial size circuits for CLIQUE. The circuit for $n$ vertices graph needs to be able to check the existence of an $1,2,...,n$ clique. Since finding $c$-cliques is in $AC^0$ for all $c$, and we assumed $AC^0\subseteq SIZE(n^k)$, we have an $n^k$ size circuit for each possible clique size, combining those will result in an $n^{k+1}$ size circuit for clique on $n$ vertices graphs, which puts $\mathsf{NP}$ in $\mathsf{P/Poly}$.
> 3 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, circuits
---


# Question
Title: Comparing the closed behaviors corresponding to finite state automata
Let $G$ be a finite state automaton (FSA) with transfer function $\delta(\cdot,\cdot)$ and initial state $q\_0$. Suppose also $\Sigma\_{G}$ represents its alphabet. Assume that its **closed behavior** is a set of strings defined as:

$L(G) := \\{s \in \Sigma\_{G}|\delta(q\_0,s) \text{ is defined in }G\\}$

Now, consider two particular FSA $G\_1$ and $G\_2$ such that $\Sigma\_{G\_{1}} \subseteq \Sigma\_{G\_{2}}$. Clearly, then we clearly have $\Sigma\_{G\_{1}}^{\*} \subseteq \Sigma\_{G\_{2}}^{\*}$. I'm wondering whether or not we `necessarily` conclude that $L(G\_{1}) \subseteq L(G\_{2})$.

To me, it's not always true. ***Am I right***?

Here is a simple example to contradict it:

in which $\Sigma\_{G\_{1}}^{\*} \subseteq \Sigma\_{G\_{2}}^{\*}$, but $L(G\_{1}) \supseteq L(G\_{2})$.

# Answer
> 1 votes
Your claim implies that $L(G)$ depends only on the alphabet of $G$, but this is clearly false. So the claim itself must be false.

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


# Question
Title: Can non-recursively enumerable languages be solved with dovetailing?
I'm a bit confused about the dovetailing concept. It seems too powerful. Could it solve non-recursively enumerable languages?

# Answer
Dovetailing is just a technique for programming Turing machines. It doesn't give Turing machines any additional power. In particular, dovetailing cannot cause a Turing machine to decide an undecidable problem, recognize an unrecognizable language, and so on.

While dovetailing might seem like an arcane technique, it is actually very similar to context-switching, which enables our computers to run many programs in parallel. This doesn't give our computers any more power – on the contrary, context-switching incurs overheads.
> 2 votes

---
Tags: computability, undecidability
---


# Question
Title: VC dimensions: Let ${x_1, \ldots, x_N}$ be $N$ labelled points on $\mathbb{R}$, then there exists a sinusoid that separates these points
(Proposition, pg 26): Let ${x\_1, \ldots, x\_N}$ be $N$ points on $\mathbb{R}$, $N \in \mathbb{Z}$, labelled either $+1$ or $-1$ , then there exists a function from the set $\\{t \mapsto \sin(\omega t)| \omega \in \mathbb{R}\\}$ that separates these points into two sets, one with all labels ${+1}$, and one with all labels ${-1}$

Does anyone see how to prove this proposition?

Right now I am using induction, however, I cannot see how it can extend to the $N$ point case.

It is also difficult to picture how this works for the $N$ point case.

# Answer
> 2 votes
Here are some ideas. Denote by $\\{x\\}$ the fractional value of $x$, and consider the function $f\_n(x) = \operatorname{sgn} (\sin 2\pi n x)$. Then:

* $f\_n(x) = +1$ iff $\\{nx\\} \in (0,1/2)$.
* $f\_n(x) = -1$ iff $\\{nx\\} \in (1/2,1)$.

Suppose first that the set of points is independent over the rationals. Weyl's equidistribution theorem shows that $\\{nx\_1\\},\ldots,\\{nx\_N\\}$ is equidistributed over $\[0,1)^N$, and in particular we can find $n$ for which $\\{nx\_i\\}$ matches the label of $i$.

Another case is $x\_i = 2^{-i}$. This case is often used to show that the collection $\\{ f\_n : n \in \mathbb{N} \\}$ has infinite VC dimension. In this case we choose $n$ so that its binary expansion corresponds to the labels of the set (details left to the reader, or see Example 3 on page 4 of these lecture notes). Using Weyl's equidistribution theorem, we can generalize this to the case $x\_i = 2^{-i} x\_0$ for arbitrary $x\_0$.

I see two possible arguments for the general case:

* Perturb the $x\_i$s slightly to new values $y\_i$ that they are rationally independent, and apply the argument above. Intuitively, if the perturbation is small enough then $\\{nx\_i\\} \approx \\{ny\_i\\}$ and by asking that $\\{nx\_i\\}$ be in (say) $(1/6,1/3)$ or $(2/3,5/6)$, we can guarantee that $f\_n(x\_i) = f\_n(y\_i)$. The difficulty with this argument is that the perturbation needs to be small as a function of $n$, and we don't know $n$ in advance, barring some uniform version of the equidistribution theorem.
* Choose a basis $r\_1,\ldots,r\_m$ for $x\_1,\ldots,x\_N$ over the rationals such that each $x\_i$ is an integer combination of the $r\_j$, and then try to apply an argument similar to that of the second case. If $m=1$ then this argument seems convincing (though details need to be checked), but the general case seems a bit more difficult.

For an interesting strengthening of the rationally independent case, see this nice paper.

---
Tags: machine-learning, learning-theory, vc-dimension
---


# Question
Title: Proving that the set of deciders is not Turing-recognizable
Let $A$ be the language consisting of descriptions of Turing machines $\\{M\_1, M\_2, \dots \\}$, where each $M\_i$ is a decider. Prove that $A$ is not Turing-recognizable.

Then suppose $A$ is Turing-recognizable and suppose $s = \\{s\_1, s\_2, \dots \\}$ is a set of all possible binary strings. Then I construct decider $D$ as follows. On input $w$, if $w$ is not equal to binary string, then reject. Else, $w$ is a binary string that is equal to $s\_i$ for some $i$. Use the enumerator $E$ to print the $i$-th output which is $M\_i$. If $M\_i$ accepts $s\_i$, $D$ is going to reject $s\_i$. Otherwise, accept $s\_i$.

But in the last step, what happens when $M\_i$ doesn't have defined transition over the alphabet $\\{0,1\\}$? Does $M\_i$ immediately enter a reject state? What should I argue?

# Answer
> 6 votes
The basic idea of the proof is to come up with a Turing machine which doesn't belong to the enumeration, hence contradicting the claim that deciders can be enumerated. To this end, we use diagonalization – for each potential machine in the enumerate, we ensure that there is at least one input on which the diagonalizing machine has a different behavior.

If the diagonalizing machine $D$ has alphabet $\Sigma$, then we already know that any machine in the enumeration with a different alphabet cannot be $D$. Therefore $D$ doesn't care much about these machines. What $D$ has to ensure is that for every machine $M\_i$ with alphabet $\Sigma$ there is an input $x\_i$ such that $D(x\_i) \neq M\_i(x\_i)$.

---
Tags: turing-machines, undecidability
---


title: Unrecognizability of HALT

text:
# Question
Title: Unrecognizability of HALT
I am currently stuck on a question from Sipser's book of automata. The question goes like this:

> Consider the following language: V = {w|w = 0a for some a which is an element of HALT} U {w|w=1b for some b which is an element of complement of HALT }
>
> Prove that V is unrecognizable? Prove that complement of V is unrecognizable?

I kinda know that to prove them we have to use contradiction but I got stuck after that and haven't been able to come up with any solution up till now. Any pointers/hints would be appreciated.

# Answer
> 3 votes
If $V$ was recognizable then the language of Halting problem could be reduced to $V$ as following.

Let $M\_V$ be a TM recognizing $V$, i.e, $M\_V$ accepts $x$ if $x \in V$. Let $u$ be some string (description of a TM). Then we run $M\_V$ on $0u$ and $1u$ by dovetailing. $M\_V$ will eventually halt on one of these inputs since $u$ is either in $HALT$ or not in $HALT$. So, when it halts we simply check: if $M$ has halted on $0u$ then $u \in HALT$, else if $M$ has halted on 1u then $u \notin HALT$. Thus this implies that $HALT$ is decidable which is impossible.

Similarly for $\overline{V}$. Let $u$ be some string (description of a TM). If $M\_{\overline{V}}$ accepts $0u$ then $u \notin HALT$. If $M\_{\overline{V}}$ accepts $1u$ then $u \in HALT$.

---
Tags: turing-machines, automata
---


# Question
Title: Is it possible to create a "Time Capsule" using encryption?
I want to create a digital time capsule which will remain unreadable for some period of time and then become readable. I do not want to rely on any outside service to, for instance, keep the key secret and then reveal it at the required time. Is this possible? If not, is some kind of proof possible that it is not?

One strategy would be based on projections of future computing capabilities, but that is unreliable and makes assumptions about how many resources would be applied to the task.

# Answer
> 5 votes
The problem is known as **timed-release cryptography**. For some references/introduction look at:

*Our motivation is the notion of "timed-release crypto", where the goal is to encrypt a message so it cannot be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to "send information into the future" ...*

# Answer
> 1 votes
I came up with a partial answer, but not strictly speaking an answer to the question as stated. I suspect this may be as close as it's possible to get, but I'm not sure.

First, we encode the capsule with the key required for decryption.

I don't know how to get around having some kind of an authority to hold the key, but it is possible to distribute that function. If we break the key into n pieces, then we can ask n authorities to hold the pieces. Then at the appropriate time would can all publish their pieces to enable reconstruction of the key.

This solution is vulnerable to any one of the n authorities being unavailable, but using m-out-of-n encoding, we can distribute the pieces to n authorities, but only require m to publish their pieces.

Even in this case, some number of authorities with an accurate clock must provide a correct key management service. Is it possible to weaken this assumption beyond the m-out-of-n suggested above?

# Answer
> 1 votes
I think this is a viable approach:

Generate a set of keys using your preferred encryption scheme using a random generated passphrase. The trick here is with the passphrase. The key is known, but we will create a time capsule using the passphrase.

Choose a passphrase such that, if we create a salted hash from it, it will take approx "n" years to calculate the passphrase given known salt and hash using today's computing power. If we want to create a 20 year capsule, estimate our computing power 20 years from now, and create a hash that will be one-month computable by either a user or a supercomputer in 20 years, depending on target for the capsule. Figure, for a 20 year time capsule,that it will be decryptable by a megacorp in 15 years, or a user in 20.

Encrypt data using keys with random passphrase, store the key and the hashed passphrase, and don't store the actual passphrase. Now preserve the data and, at some point in the future, you will hopefully have the computing power to recover your data!

# Answer
> 0 votes
I'm no cryptographer, just an engineer, so my solution is more physical than computational, but let me have a try anyway. I propose the following procedure:

1. Generate the asymmetric key pair
2. Encrypt the plaintext message using the public key
3. Store the private key inside the volatile memory of a microcontroller, and make it output the key only after certain time elapses.
4. Destroy all other copies of the private key
5. Bundle the cyphertext and the microcontroller together, and wait.

The obvious question then arises: Why bother with encryption when you could just store the plaintext message in the chip? The answer to this is that this way, the plaintext can be arbitrarily long, without hitting the storage capacity of the chip, because only the fixed-length key is stored there. Also, you can keep a copy of the public key, generating more messages with it later, which are then unlocked at the same time. But that's about it.

To make this even more secure, you could attach a light sensor to the chip and enclose the assembly in a light-proof case (or have a switch attached to the door, or some other tamper detection mechanism), where exposing the sensor to light will trigger key erasure. This is to prevent obtaining the key using invasive methods such as etching. Some chips also have their silicon layers structured in a way to make invasive reading nearly impossible, by putting other essential circuitry above the memory, to obscure the individual bits.

---
Tags: cryptography, encryption, digital-preservation
---


# Question
Title: Could a modification of Krom's proof system be used to solve 3-SAT in polynomial time?
A literal is a nonzero integer, and we define $\sim x = -x$.
A clause is a nonempty set of literals.
A CNF is a set of clauses.
A K-rule is a pair $(F,C)$ where $F$ is a CNF and $C$ is a clause.
A Krom-style proof system (KPS) is a set of K-rules.
If $S$ is a KPS, then an $S$-proof of $C$ from $F$, or an $(S,F)$-proof of $C$, is a sequence $\langle C\_1,..,C\_n\rangle$ of clauses such that $C = C\_n$ and for all $1\le i\le n$, either $C\_i \in F$ or there is a K-rule $R = (G,A) \in S$ and a function $f : \\{x,\sim x : x \in B \in G \lor x \in A\\} \rightarrow \mathbb{Z}\_{\ne 0}$ which respects negation such that letting $g(B) := \\{f(a) : a ∈ B\\}$, we have $C\_i = g(A)$, and for all $B \in G$, there exists some $j \< i$ with $C\_j = g(B)$.
For fixed $S$, the language $\\{(F,C) : F \vdash\_S C\\}$ is polynomial-time decidable:

```
read inputs F and C
if C ∈ F
    return true
let D = {x1,~x1,..,xn,~xn} be the set of literals occuring in F or C, and their negations
Contin := true
while Contin
    Contin ← false
    for (G,A) in S
        for h : {abs(x) : x ∈ B ∈ G ∨ x ∈ A} -> D # there are |D|^c such functions
            f(x) := (x > 0 ? h(x) : -h(-x))
            g(B) := {f(a) : a ∈ B}
            for B in G
                if g(B) ∉ G
                    continue in the for-loop where h is chosen
            if g(A) ∉ F
                push g(A) to F
                Contin ← true
if C ∈ F
    return true
else
    return false

```

$S$ is sound if for all CNF's $F$ and clauses $C$, the existence of an $(S,F)$-proof of $C$ implies that $F \vDash C$.
$S$ is complete for a class $\Gamma$ of CNF's if for all $F \in \Gamma$ and $C$, if $F \vDash C$ then $C$ is $(S,F)$-provable.
No KPS is complete for full $SAT$, since any clause of the form $\\{-1,1,2,3,..,n\\}$ is tautological, but for any system $S$, $sup\\{|A| : (\emptyset,A) \in S\\}$ is only finite, making the clause $(S,\emptyset)$-unprovable for sufficiently large $n$.
$\\{(\\{\\{1\\},\\{-1\\}\\},\\{2\\})\\}$ is complete for $1$-$SAT$, and represents the rule $a,\sim a \vdash b$.
$\\{(\emptyset,\\{1,-1\\}),(\\{\\{1\\}\\},\\{1,2\\}),(\\{\\{1,2\\},\\{-1,3\\}\\},\\{2,3\\})\\}$ is complete for $2$-$SAT$, and represents the system consisting of the rules (1) $\vdash a\lor\sim a$, (2) $a\lor a \vdash a\lor b$, and (3) $a\lor b, \sim a\lor c \vdash b\lor c$.
**Question 1.** Is it known that no sound KPS can be complete for $3$-$SAT$?
If such a KPS was found, it would imply $P=NP$ and the polynomial-boundedness of natural propositional proof systems.
I am particularly interested in the completeness of the system $S\_3 = \\{(\emptyset,\\{1,-1,2\\}),(\\{\\{1,2,3\\},\\{1,2,4\\},\\{-3,-4,5\\}\\},\\{1,2,5\\})\\}$ for $3$-$SAT$, where the main rule corresponds to the fact that if $a \land b \Rightarrow c$, $a \land b \Rightarrow d$, and $c\land d\Rightarrow e$, then $a\land b\Rightarrow e$.
**Question 2.** Can $S\_3$ be shown to be complete for $3$-$SAT$, or at least some restricted class thereof such as $Horn$-$SAT\cap 3$-$CNF$ or the pigeonhole principle?
An $(S,F,d)$-proof is the same as an $(S,F)$-proof $\langle C\_1,..,C\_n\rangle$, except that we have a function $h : \\{1,..,n\\} \rightarrow \\{0,..,d\\}$, and the last part of the old definition, namely "$C\_j = g(B)$", is strengthened by additionally requiring that $h(j) \< h(i)$.
So far, I have been able to show that if $\langle C\_1,..,C\_n,C\_{n+1}\rangle$ is an $(S\_3,F\cup \\{\\{a,b,c\\}\\})$-proof of $C\_{n+1} = \\{d,e,f\\}$ with $C\_1,..,C\_n \in F$, then for $x=a,b,c$ there exists an $(S\_3,F\cup\\{ \\{\sim d\\}, \\{\sim e\\}, \\{\sim f\\}\\},5)$-proof $\langle D\_1,..,D\_{23}\rangle$ of $\\{\sim x\\}$.
However, the algorithm given above takes $O(n^8)$ steps on the RAM model of computation in the case of $S\_3$. Krom's original algorithm for 2-SAT had a running time of $O(n^3)$, but this upper bound has since been improved to $O(n)$, even if we want to find a satisfying assignment when one exists.
**Question 3.** How quickly can we solve the $S\_3$-provability problem? If this system happens to be complete for $3$-$SAT$, how quickly can we find satisfying assignments to consistent formulae?

# Answer
> 3 votes
Any proof in KPS (with whatever rules) can be rephrased as a sequence of lines, each of which is either a clause or follows from preceding lines according to one of finitely many inference rules. Additionally, the lines come from one of finitely many "patterns" (formulas with placeholders to variables), and so all proofs are polynomially bounded.

Suppose that the maximum depth of a pattern is $d$. Then your proof is also a proof in depth $d$ Frege. It is known that the pigeonhole principle needs $2^{\Omega(n^{1/5^d})}$ lines to refute in depth $d$ Frege. This implies that KPS systems cannot be complete for 3SAT, since all proofs in KPS are polynomially bounded.

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


title: What is decider?

text:
# Question
Title: What is decider?
According to Wikipedia

> In computability theory, a machine that always halts—also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a Turing machine that halts for every input.

My understanding of decider is that a machine is a decider if it always halts with output $0$ or $1$ (or whatever you prefer meaning "YES" and "NO"). However, I am confused by the definition that decider is a Turing machine that always halts since there are machines that do always halt with different than $0$ and $1$ outputs. For example, the Turing machine with the tape alphabet $\Sigma=\\{a,b,c,d,e\\}$ and simply printing as output the first symbol of the input has five different outputs.

Question: Do we need to restrict the output of deciders to only two different symbols or strings denoting "YES" and "NO"?

# Answer
> 9 votes
The term *decider* doesn't really have a standard meaning. In fact, it is lamentable that Sipser chose the terms *decider* and *recognizer*, since they seem to confuse students.

Intuitively, a decider should be a Turing machine that given an input, halts and either accepts or rejects, relaying its answer in one of many equivalent ways, such as halting at an ACCEPT or REJECT state, or leaving its answer on the output tape.

A similar concept is a total Turing machine, which is a machine that halts on every input. A total Turing machine can be understood to compute a function (the answer is given on the output tape), or it can accept a language (using any of the semantics considered in the preceding paragraph).

It's really up to you whether a *decider* is allowed to output anything other than 0 or 1, and more generally, whether it can compute an arbitrary function, or whether it can only compute a Boolean function. The term is simply ambiguous. Sometimes you can tell the meaning from context, and in textbooks you will hopefully find a definition.

In contrast, *total Turing machines* means the same for everybody. But the ambiguity hasn't disappeared – it is now not completely clear what is the language accepted by a total Turing machine. If the Turing machine has ACCEPT/REJECT annotation for its halting states, then you can define the language this way. Or you can define it via the output. You can even say that a total Turing machine accepts a language only if its output is always 0 or 1. It's really up to you.

Whatever definitions you use, as long as they are reasonable, the same basic theorems of computability theory will hold. In a sense, the exact definitions do not matter, and this is why there is such a great variety of them. Wikipedia presents one possible definition, but your course or textbook could be using another definition which is formally inequivalent but in practice completely equivalent, like two versions of C++.

Assuming you are taking a course of self-learning from a textbook, I suggest not using Wikipedia for basic definitions. Instead, use the formal definitions that are in the textbook or that were given in class.

---
Tags: computability, turing-machines
---


title: Number of 2-3 trees of depth 4

text:
# Question
Title: Number of 2-3 trees of depth 4
I have a task to find a number of 2-3 trees... I don't quite know what it means, I'm asked to: find the number of 2-3 trees of depth $4$? Is there a specific way to find number of 2-3 trees of depth $n$?

Thanks!

# Answer
Here is one interpretation of this question. We want to count rooted trees with ordered children in which each internal node has either 2 or 3 children.

Denote by $T\_d$ the number of 2-3 trees of depth at most $d$, so $T\_0 = 1$ (the tree consisting of a single node) and $T\_1 = 3$ (the tree consisting of a a single node; a root with two children; a root with three children). More generally, a 2-3 tree of depth at most $d$ is either just a single node or consists of a root with two or three children, each of which is a 2-3 tree of depth at most $d-1$. Therefore $T\_d = 1 + T\_{d-1}^2 + T\_{d-1}^3$.

Finally, the number of 2-3 trees of depth *exactly* $d$ is $T\_d - T\_{d-1}$. For example, the number of 2-3 trees of depth exactly 1 is $T\_1 - T\_0 = 3-1 = 2$.
> 2 votes

---
Tags: trees, combinatorics
---


# Question
Title: Estimating time cost for sorting algorithm given the average time for sorting of 1000 elements
Assuming that an implementation of a sorting algorithm takes 0,01 seconds to sort 1000 elements, how long would it take to sort 100 million elements?

What do I need to know about my the algorithm to estimate the time? Is its time complexity given in $\mathcal{O}$-notation sufficient to find that out?

In my example the algorithm is Bubblesort, of which I know that it is extremely inefficient for sorting long lists and I also know that the average case is $\mathcal{O(n^2)}$, however I am unsure how much depends on the concrete implementation, which is not given. I also am interested in the general approach towards the problem.

My train of though is that since Bubblesort is $\mathcal{O(n^2)}$ in the average case, the time cost is $c\cdot n^2$ for some constant time cost of an elementary operation $c$ (can I even assume that it is constant?). So $c \cdot 1000^2=0,01 \iff c=10^{-8}$, which would instantly give me acces for time cost for any list length $n$. I am aware that $\mathcal{O(n^2)}$ does not mean that $n^2$ is the only factor in the cost equation, but it is the leading one as $n$ grows. Is this the correct approach?

# Answer
It is in general impossible to interpolate the running time of algorithms even if you know their asymptotic running time. There are many reasons for this – here are two:

1. The running time of an algorithm is usually composed of many different terms. For example, it could be of the form $An\log n + Bn$. This running time doesn't scale like $n\log n$, since for small $n$ the $Bn$ term might be important, whereas for large $n$ it might be negligible.
2. Resource access times do not scale in $n$, but rather jump. When $n$ is small, everything fits into the smallest cache, so data access is very quick. When $n$ gets larger, you need to use a larger cache, so all at once data access becomes slower. When $n$ gets even larger, you need to use main memory (or even beyond), and data access becomes even slower.

In some cases these reasons do not apply. For example, you might be interested in values of $n$ for which one part of the algorithm clearly takes almost all the time, and you can easily estimate how it scales in $n$; and furthermore, memory consumption is minimal so increasing $n$ doesn't result in reduced data access behavior. In such cases it is possible to extrapolate the running time.

An extreme example is when you are estimating some quantity empirically, and $n$ is the number of samples. The running time of such a program scales linearly with $n$.
> 2 votes

---
Tags: sorting
---


# Question
Title: How to find the equivalence classes of a regular language
Given a language $L=\\{ 0^m1^n | m \neq n \\}$ over $\Sigma = \\{ 0,1 \\}$, how would one go about characterizing the equivalence classes of this language?
I know there isn't a formal algorithm for that, but still, can some steps always be taken?

# Answer
> 1 votes
You have to be creative. In this case, the equivalence classes are:

* $X\_a = \\{0^a\\}$ for $a \geq 0$.
* $Y\_a = \\{0^{n+a} 1^n : n \> 0\\}$ for $a \geq 0$.
* $Z = \\{0^n 1^m : m \> n \\}$.
* $W = \\{w : w \text{ contains } 10\\}$.

We can construct an infinite DFA to show that each of these classes consists of equivalent words:

* The initial state is $X\_0$.
* The accepting states are $X\_a,Y\_a$ for $a \neq 0$ and $Z$.
* $\delta(X\_a,0) = X\_{a+1}$, $\delta(X\_0,1) = Z$, $\delta(X\_{a+1},1) = Y\_a$.
* $\delta(Y\_a,0) = W$, $\delta(Y\_0,1) = Z$, $\delta(Y\_{a+1},1) = Y\_a$.
* $\delta(Z,0) = W$, $\delta(Z,1) = Z$.
* $\delta(W,0) = \delta(W,1) = W$.

This also shows that the classes cover all of $\Sigma^\*$. Finally, in order to show that these are the equivalence classes, we need to show that any two classes have a separating word:

* $X\_a,X\_b$: $1^a$.
* $X\_a,Y\_a$: $0$.
* $X\_a,Y\_b$: $0$.
* $X\_a,Z$: $1^a$.
* $X\_a,W$: $0$.
* $Y\_a,Y\_b$: $1^a$.
* $Y\_a,Z$: $1^a$.
* $Y\_a,W$: $1^{a+1}$.
* $Z,W$: $\epsilon$.

---
Tags: regular-languages
---


# Question
Title: If $L$ is recursively enumerable (or recursive) then so is $L′$
Given a language $L \subset \\{0, 1 \\}^\*\\#\\{0, 1 \\}^\*$ and a language $$L'=\\{u \in \\{0,1\\}^\* | \textrm{ There is a word }w \in \\{0,1\\}^\* \text{, so } u\\#w \in L\\}$$

Prove or disprove:

1. If $L$ is recursively enumerable, then $L'$ is recursively enumerable.
2. If $L$ is recursive, then $L'$ is recursive.

My idea for 1:
Since we know by the definition of $L'$ that for every $u \in L'$, there must be a $w \in \\{0,1\\}^\*$, so $u\\#w \in L$. So we can construct a Turing-machine $M\_f$, which decides the function $f: \sum ^\* \to \sum ^\*$ where $\sum^\*$ is the alphabet, so $$u \in L' \iff f(u) = u \\# w \in L$$ So $L'$ is reducible with $L' \le L$, and because $L$ is recursively enumerable, $L'$ is recursively enumerable.

Regarding the second questions, I would argue the same but I think it is possible to construct a more detailed turing machine. Any hints?

# Answer
The second item is in fact false. Consider the language $L$ consisting of $u\\# w$ such that the $u$th Turing machine halts within $w$ steps. This is recursive, but $L'$ is the language corresponding to the halting problem.
> 3 votes

---
Tags: formal-languages, computability, reductions, closure-properties
---


# Question
Title: Using reduction to prove that a given language is not recursively enumerable
Let the language $L$ be as follow ;

$$L=\\{\langle M\_1 \rangle \langle M\_2 \rangle \mid L(M\_1) \cap L(M\_2)=\emptyset \\}$$

$\langle M\_1 \rangle$ and $\langle M\_2 \rangle$ are the encoding of the Turing machine $M\_1$ and $ M\_2$.

Using Reduction, I have to prove that $L$ is not recursively enumerable.

In order to prove that I have to find a non-recursively enumerable language $S$ so that: $$S \leq L$$ One of the non recursively enumerable that I had in my lesson, were those : $${H\_{\varepsilon}^\complement}=\\{\langle M \rangle \mid \text{M does not halt on empty input} \\}$$ and ; $${H\_{all}}=\\{ \langle M \rangle \mid \text{M halts on each input} \\}$$

$$ \text{Let then } S = {H\_{all}}$$

I have to prove in this case that ; $${H\_{all}} \leq L $$

let then ; $$ f : {H\_{all}} \rightarrow L \\ \langle M \rangle \mapsto \langle M \rangle \langle M^\complement \rangle$$

In this case $M^\complement $ simulate M in each input , when $M$ accepts/rejects, $M^\complement $ rejects/accepts.

$\texttt{case 1}$

$\langle M \rangle \in {H\_{all}} \Rightarrow \text{M halts on each input and accepts/rejects} \Rightarrow M^\complement\text{ hatls on each input and rejects/accepts} \Rightarrow L(M) \cap L(M^\complement)= \emptyset $

$\Rightarrow \langle M \rangle \langle M^\complement \rangle \in L $

$\texttt{case 2}$

$\langle M \rangle \not\in {H\_{all}} \Rightarrow \text{M does not halt on all inputs} \Rightarrow M^\complement\text{ halts on some inputs} \Rightarrow L(M) \cap L(M^\complement) \neq\emptyset $

$\Rightarrow \langle M \rangle \langle M^\complement \rangle \not\in L $

somehow i think , the contruction of the function of is not right, does anyone maybe have an other idea or an other S to choose ?

# Answer
> 4 votes
Assume that $L$ is recursively enumerable. We can reduce the Halting problem to $L$ as following. Given $\langle M, w \rangle$, create a TM $M'$ which halts only on the input $w$, and infinitely loops if the input is different from $w$. Clearly $L(M') = \\{w\\}$ and $L(M) \cap L(M') = \emptyset \iff \langle M,M' \rangle \in L \iff \langle M, w \rangle \notin HALT$. This shows that $\overline{HALT}$ is recursively enumerable. Since $HALT$ is also r.e. it follows that $HALT$ is decidable which is impossible. Thus $L$ is not recursively enumerable.

---

$HALT = \\{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ halts on input } w \\}$.

---
Tags: computability, turing-machines, enumeration
---


# Question
Title: Which data structure to use for accessing min/max in constant-time?
I need a data structure which can include millions of elements, minimum and maximum must be accesable in constant time and inserting and erasing element time complexity must be better than linear.

# Answer
A basic data structure that allows insertion and deletion in time $\Theta(\log n)$ are balanced binary search trees. Their memory overhead is reasonable (in case of AVL trees, two pointers and three bits per entry) so millions of entries are no problem at all on modern machines.

Note that in a search tree, finding the minimum (or maximum) is conceptually easy by descending always left (right) starting in the root. This works in time $\Theta(\log n)$, too, which is too slow for you.

However, we can certainly store pointers to these tree nodes, similar to front and end pointers in double-linked linear lists. But what happens when the elements are deleted? In this case, we have to find the in-order successor (predecessor) and update the pointer to the minimum (maximum). Finding this node works in time $O(\log n)$ so it does not hurt deletion time, asymptotically.

You can, however, enable time $O(1)$ deletion of minimum and maximum by *threading* the tree, that is maintaining -- in addition to the binary search tree -- a double-linked list in in-order. Then, finding the new minimum/maximum is possible in time $O(1)$. This list requires additional space (two pointers per entry) and has to be maintained during insertions and deletions; this does not make the asymptotics worse but certainly slows down *every* such operation (I leave the details to you). So you have to trade-off the options given your application, that is which operations occur more often and which you want to be fastest.

Note that trees, as all linked structures, tend to be bad for memory hierarchies since they don't necessarily preserve data locality. If your sets are so large that they don't fit into cache completely, you should check out B-trees which are designed to minimise page loads. The above works with them, too.
> 12 votes

# Answer
The name for the abstract data structure that you're interested in is a "double-ended priority queue" or sometimes "priority deque".

A min-priority queue, as you probably know, is an abstract data structure which supports the following set of operations:

* insert (add an item)
* findMin (find the item with the smallest value)
* deleteMin (remove the item with the smallest value)

This is the minimal set; other typical operations may include:

* delete (remove any item)
* decreaseKey (alter an item so that its key is smaller)
* merge (merge two priority queues into one)

For the purpose of time analysis, it is usually assumed that all you have to compare keys is a binary comparison operator. You can also dually define a max-priority queue, where you're interested in the largest value rather than the smallest, by simply inverting the sense of the comparison operator.

A double-ended priority queue is one that supports querying and efficiently removing the minimum or maximum value.

If I'm reading you correctly, this is the set of operations that you definitely want, along with their time complexities:

* insert - better than O(n)
* findMin - O(1)
* findMax - O(1)
* deleteMin - better than O(n)
* deleteMax - better than O(n)

and there is one operation that you possibly want:

* delete - better than O(n)

I'm going to ignore this operation because it complicates things. To delete an arbitrary item, you must locate an arbitrary item. Some priority queue data structures (e.g. Fibonacci heaps) support the concept of a "location" (like an iterator in C++) which stays valid no matter what modifications you do to the queue (apart from deleting the item in question, obviously), but many do not, because items can move around in the data structure. If you really need this operation, then a variant of binary search trees which supports findMin and findMax in constant time is probably what you need. This turns out to be a very simple and pleasant exercise in algebra; see \[1\] for details, including Haskell source code.

There are a few obvious ways to do this if you already have a priority queue data structure available by maintaining a min-queue and a max-queue, and maintaining correspondences between them. See \[2\] for some details on how you might go about this.

Most of the other interesting options are based on binary heaps, but combine min-heaps and max-heaps in one data structure, such as min-max heaps \[3\] and interval heaps \[4\].

By the way, if your keys are integers (not just binary-comparable blobs) then you can probably do better. vEB trees, for example, generalise to double-ended priority queues in a straightforward manner.

---

1. A fresh look at binary search trees by R. Hinze (2002)
2. Correspondence based data structures for double ended priority queues by K.-R. Chong and S. Sahni (1998)
3. Min-max heaps and generalized priority queues by M. D. Atkinson et al. (1986)
4. Data Structures, Algorithms, and Applications in C++ (Chapter 9.7) by S. Sahni (1998)
> 4 votes

# Answer
You should look into https://en.wikipedia.org/wiki/Van\_Emde\_Boas\_tree. It comes with some compromises, mostly your elements need to be integers and memory consumption may be high (but may be way lower than for binary trees for dense keys). Min and max are constant time, insert/delete/successor are O(log log M), M being key space. Careful implementation may out-preform a binary tree by a factor of 10 for millions of keys (mostly if they are dense).
> 3 votes

# Answer
One of the best heaps to use for that purpose is Fibonacci Heap. It has O(1) insert and O(1) findMin, together with O(1) decreaseKey, if you need it.

If you really need deleteMin and findMin consequtively (meaning you find multiple minimums) then I would not recommend using a heap. QuickSelect algorithm (which is O(n)) for searching all the minimums has worked faster for me.

http://en.wikipedia.org/wiki/Quickselect
> 0 votes

---
Tags: data-structures, efficiency
---


# Question
Title: Objective function and constraint satisfaction over a set of multi-attributes elements
I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints.

To illustrate my point, I'll try to come up with an example.

A bag contains several items with the following attributes:

* Value (Int)
* Size (Int)
* Material (Enum)
* Origin (Enum)

As an example, we can imagine a bag consisting of the following items:

```
value     size     material    origin
    4        1         wood        FR
    4        2        stone        US
    3        3         gold        JP
    2        2         wood        FR
  ...      ...          ...       ...

```

The goal is to maximize the total Value, while at the same time respecting a set of constraints. An example set of constraints would be:

```
total size < 80
between 20 and 35 items in total
at least five elements with origin FR
at least two elements with material wood OR at least two elements with material stone
strictly less elements with material gold than elements of material stone
no more than 5 elements with size > 10

```

Below are some approaches I've thought about, and the reason why I can't use them directly:

* (Integer) Linear Programming: here we're not dealing with the full space of Integers, but instead only with the values found in the bag (and tied to the other properties for each item)
* Stochastic Constraint Satisfaction: it would be easy to stochastically come up with a selection of Items which respects the constraints, but here we're not looking for *any* solution, instead we're looking for *the* solution which yields the highest total Value, which would need us to exhaustively list all possible satisfying solutions before picking the one with highest value (which may be a very inefficient approach)
* SMT solver: I think it could be the way to go, but so far I can't see how to model the link between the constraints, the objective function and the bag of elements

Can you think of an approach to solve this kind of problems?

# Answer
I don't see any problem with modeling this as an integer linear program, for example:

```
maximize V.x
st:
1) s.x < 80
2) 20 <= e.x <= 35
3) FR.x >= 5
4a) Wood.x + 2 - 2W >= 2
4b) Stone.x + 2W >= 2
5) Gold.x - Stone.x < 0
6) Size10p.x <= 5
x[i] ∈ {0, 1}
W ∈ {0, 1}

```

Where `.` is the dot product, `x` is a binary vector indicating which items to take, `e` is the vector of all-ones, `FR` is a boolean vector where an element is 1 iff the corresponding item is from France, `Wood` is a boolean vector that indicates that the material wood, etc. `Size10p` indicates that the item has a size higher than 10.

I've made all the left-hand sides of dot products the constant vector, so you can easily see that there are no sneaky quadratic constraints.

Most of the constraints are obvious, but constraint 4 is a bit trickier. It involves a disjunction, and uses an extra binary variable to choose which "side" of the disjunction to take. The other half is then trivially satisfied, by either adding 2 and *not* also subtracting 2 (`W = 0`, not taking the wood-side of the disjunction) or by just adding 2 (`W = 1`, taking the wood-side).

> here we're not dealing with the full space of Integers, but instead only with the values found in the bag

This is usually not a problem, since you can binarize constraints of the form `v ∈ some enum` to `v1 = [v == item1], v2 = [v == item2]` etc combined with `v1 + v2 + ... = 1`. But I did not even need that here, the decision is just "do I take this item or not", and things such as "item has property 'Gold'" are just constant booleans.

More tricks are available in other answers, for example Express boolean logic operations in zero-one integer linear programming (ILP).
> 1 votes

---
Tags: linear-programming, constraint-satisfaction, smt-solvers
---


# Question
Title: Finding integrality gap for maximum weight independent set
One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my LP relaxation.

As far as my knowledge goes, integrality gap for maximization problem is the the maximum ratio cost(LP)/cost(ILP) over all instances of a problem. But I've been googling for a little bit, and most examples only showed how to get a lower bound of integrality gap by taking some arbitrary instance. Is it possible to get an exact ratio?

# Answer
> 3 votes
Suppose you prove that an upper bound on the integrality gap is $\alpha$. The goal is to “create” an instance (weighted graph, or better yet, a family of weighted graphs) where the value of the optimal LP solution is $\alpha$ times the value of the ILP solution.

Independent set ILP $$O\_{ILP}=\max\sum\_{v\in V}x\_{v}\cdot w(v) $$
such that
$$x\_{v}+x\_{u} \leq 1\ \ \ \forall u,v\in V$$ $$x\_{v}\in\\{0,1\\} \ \ \forall v\in V$$

The relaxation is straight forward. say the value of the optimal solution to the LP is $O\_{LP}.$ Now, you want to upper bound $ O\_{LP}/O\_{ILP}.$ To do this, try to consider a rounding scheme that converts a solution for the LP into a feasible solution for the corresponding ILP. One such scheme involves reasoning about the constraints, that is $x\_{v}+x\_{u}\leq1$ for every edge in G. This implies that at least one of $x\_{u}$ or $x\_{v}$ is atleast $1/2$, and therefore all vertices in $v\in V$ such that $x\_{v}\>\frac{1}{2}$ is an independent set in $G$. I'll leave it to you to reason about how to compare $O\_{LP}$ and $O\_{ILP}$, (i.e. determine the maximum of the ratio $\alpha=\max O\_{LP}/O\_{ILP}$), and to find an instance where $O\_{LP}$ is atleast $\alpha.$

---
Tags: optimization, linear-programming
---


# Question
Title: Sorting an array of length $n$ in $O(m+n)$ time
I need to find a method to sort an array in $O(m+n)$ time complexity. I understand it should be a variation on Radix sort, however I am not familiar with it or its implementation...

> *Input*: an array $A$ of length $n$, containing values from $-m$ to $m$
>
> *Output*: a sorted array $A$

Any suggestions will be appreciated, thanks!

# Answer
Use counting sort. In $O(n)$, count the number of elements of each value, and then in $O(m+n)$ go over the histogram and translate it to the sorted array.
> 1 votes

---
Tags: time-complexity, sorting, arrays, radix-sort
---


title: Sorting an array in linear time

text:
# Question
Title: Sorting an array in linear time
I need to find a method to sort an array in $O(n)$ time complexity. I saw this link, however I'm not sure how to apply it to the elements I need.

> *Input*: an array $A$ of length $n$, containing values from $1$ to $n^2$
>
> *Output*: a sorted array $A$

Can someone explain in pseudocode or in words how to do this?

# Answer
This is a textbook application of radix sort.

Think of the inputs as 2-digit numbers in base $n$. Using a stable version of counting sort, sort the numbers first according to the least significant digit and then according to the most significant digits. Each pass takes $O(n)$, for a total running time of $O(n)$.

The same approach works for numbers up to $n^k$, and takes time $O(kn)$.
> 5 votes

---
Tags: time-complexity, sorting, counting, radix-sort
---


# Question
Title: Proving that vertex labeling is NP-complete
Given a graph $G=(V,E)$, all the vertices $v \epsilon V$ are labeled with values from $\\{1,2,...\ldots n\\}$ where $|V| = n$ such that for all edges $(x,y) \epsilon E$ such that $|label(x) - label(y)| \ge 2$. We have to determine whether such a labeling is possible for a graph.

Now I have to prove that doing so is a NP-complete problem. While showing that it belongs to NP is straightforward, I am unable to think of which NP-complete problem to be considered for reduction in polynomial time to this problem as part of the proof?

# Answer
> 1 votes
Given a graph $G$, consider its complement $G'$. The graph $G'$ is a yes instance of your problem if its vertices can be ordered so that adjacent vertices are not connected by an edge in $G'$. In other words, $G'$ is a yes instance of your problem if the vertices of $G$ can be ordered so that adjacent vertices are connected. So $G'$ is a yes instance of your problem if and only if $G$ has a Hamiltonian path.

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


# Question
Title: How are codes like 5421 and 2421 unique?
For the number 6, if I need to represent it in 5421 code form, should I code it as 1001 or 0110? Why should I choose the one over the other?

Similarly for the number 5 in 2421, is it 1011 or 0101?

Edit 1:

In a weighted binary code, the name of the code indicates the weight assigned to each place.

So if the code is 8421, the number 9 would be written as 1001 (8\*1 + 4\*0 + 2\*0 + 1\*1=9). And the number 5 would be 0101 (8\*0 +4\*1 +2\*0 +1\*1=5). In each case, no other combination of weights add up to the values (9 and 5).

Edit 2:

But for 5421, can the number 5 be represented as 1000 (5\*1+4\*0+2\*0+1\*0=5) as well as 0101(5\*0 + 4\*1 + 2\*0 + 1\*1 = 5)? Which one should be chosen? Similarly for 2421, which one to choose between 1011 (2\*1 + 4\*0 + 2\*1 + 1\*1 = 5) and 0101 (2\*0 + 4\*1 + 2\*0 + 1\*1 = 5)?

# Answer
Codes like 5421 and 2421 are not unique, and this is one of their advantages. For example, 2421 is *self-complementing*: computing the 9-complement of a digit is the same as negating its bits. In textbooks you can find tables in which the authors choose one possible code for each digit, but this choice is arbitrary, and you might find different choices in different textbooks.

Let me also mention that BCD has been gradually losing favor, and I expect only old hardware to use anything other than 8421 (if at all). Most of the interest in BCD is historical, since modern architectures don't use BCD. I suspect that material about BCD is there mostly because of inertia, though BCD might still be used in conservative industries such as banking.
> 2 votes

---
Tags: code-generation
---


# Question
Title: Growing multiples of variable combinations
I need to find growing combinations of variables a, b, c etc. I don't know names of math things in English well, so my description of the problem will be in pseudocode. This is for a programming problem, but I want to understand the underlying mathematics. I would highly appreciate proper names of techniques used so I can look them up further.

Lets say we have a list of variables

```
L (a, b, c)

```

And one single variable `l` which is the maximum desired count of a single variable from `L`.

I need to find every combination of elements from `L` multiplied by numbers from 0 to `l`.

So, for `l = 3` I expect the following result:

```
1a0b0c
0a1b0c
0a0b1c
1a1b0c
1a0b1c

```

... and so on until ...

```
3a3b3c

```

# Answer
You can think of these combinations as 3-digit numbers in base $l+1$. For example, if $l=9$ then the solutions to your problem are in one-to-one correspondence with 3-digit decimal numbers, from 000 to 999. There are in total $(l+1)^3$ of them.

As an aside, it is not clear why you omitted `0a0b0c`.
> 2 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Communication complexity of string matching
let us consider Alice and Bob communicate over channel bit by bit. They have one string over $\\{0,1\\}^{\*}$. Let $x$ (uniformly at random) be the string that Bob have and $y$ be the string that Alice have. They want to check whether there strings are same or not.

On simple algorithm is exchange $n$ bits one by one. We want to solve this problem with few bits exchanged between Alice and Bob.

**My Idea :** We will randomly select $k = O(\log {n})$ many bits and exchange only these bits. In this probability of error is going to be less than $1/2^{k}$ (because probability of making error for one bit is 1/2) and as each time we are randomly selecting the bits overall probability of error will be less than $\frac{1}{2^{k}}$.

**Question :** Is my solution optimal one to solve the problem described above?

# Answer
> 3 votes
By simply exchanging random indices you cannot hope to do better than $\Omega(n)$ communication if you want constant error probability. If the strings differ in only a single bit, and you exchange $k$ indices, then the probability of finding the index in which they differ is $\frac{k}{n}$, so if you want this to be constant you must have $k=\Omega(n)$.

The randomized communication complexity can indeed be reduced to $O(\log n)$, but you're going to need stronger arguments. One way to do this is to encode both words with an error correcting code having a large distance, and then use your algorithm (naive sampling) on the codewords.

To elaborate on the above idea, the choice of code doesn't really matter, as the only property you need in order to make naive sampling work is large distance. One example is using Reed-Solomon, given $s\in\\{0,1\\}^n$, think of it as a string of length $k$ over $\mathbb{F\_q}$, with $q=n$ and $k=\frac{n}{\log n}$. In that case you can think of $s=s\_0,...,s\_{k-1}$ as the polynomial $P\_s=s\_0+s\_1x+...+s\_k x^{k-1}$ over $\mathbb{F}\_q$. If $s\_1\neq s\_2$ then their corresponding polynomials agree on at most $k-1$ points in $\mathbb{F}\_q$, which means they will differ on at least $n-(k-1)=n\left(1-\frac{1}{\log n}\right)+1$ points in $\mathbb{F}\_{q=n}$. Thus, with high probability, $P\_{s\_1},P\_{s\_2}$ will disagree on a random point in $\mathbb{F}\_q$. This protocol requires you to send three elements in $\mathbb{F}\_q$ (a point and both polynomials evaluations on it), which results in $O(\log q)=O(\log n)$ communication.

This is only one option, there are many randomized protocols for equality. One example is using a simple public coins protocol, in which both parties share two random strings $r,r'\sim U\_n$, and exchange the values of $\langle xr,r'\rangle, \langle yr,r'\rangle$. This succeeds with probability $\frac{1}{2}$, and you can turn it into a private coin protocol with logarithmic overhead in communication, see these notes for details. Another option is to choose a prime $p\le poly(n)$ at random, and exchange $x,y\bmod p$. If $x\neq y$ then with high probability $p$ will not divide $x-y$.

---
Tags: complexity-theory, communication-complexity
---


# Question
Title: What's the difference between subtyping and inheritance?
In object-oriented programming, I have learned the concept of `subtyping` and `inheritance`.
I thought they're the same thing, in the beginning. But I was told that they're totally different.

So what's there difference? What's there relationship?

# Answer
> 2 votes
See the following discussions in other stack exchange groups.

See discussion in https://stackoverflow.com/questions/23592131/what-is-the-difference-between-subtyping-and-inheritance-in-oo-programming

Also see https://cstheory.stackexchange.com/questions/10620/how-does-inheritance-differ-from-subtyping

However there is some differences of opinion. See Inheritance Is Subtyping as well as Inheritance Is Not Subtyping

---
Tags: object-oriented
---


# Question
Title: Difference between fixed-to-variable length codes and variable-to-fixed length codes?
I am a bit confused by the difference between the two. Can someone clarify the difference between the two?

# Answer
> 2 votes
A fixed-to-variable length code is a code that takes a string in $\cal X^\*$, partitions it into chunks of fixed length $n$, and replaces each chunk $w$ by some codeword $C(w)$ whose length isn't fixed. The classical example is prefix codes. A prefix code such as Huffman's code replaces each symbol $\sigma \in \cal X$ by a codeword $C(\sigma)$, with the aim of minimizing $\mathbb{E}\[|C(\sigma)|\]$ with respect to some distribution on $\cal X$. We can obtain a better rate by applying Huffman coding on $k$-tuples of inputs. This corresponds to a fixed-to-variable length code that encodes each word $w$ of fixed length $k$ by a codeword $C(k)$.

A variable-to-fixed length code is a code that takes a string in $\cal X^\*$, breaks it into pieces of variable length, and replaces each piece into a word of fixed length. The classical example is Lempel-Ziv encoding with fixed dictionary size. Lempel-Ziv breaks its input into chunks, where each chunk extends a word in the dictionary by one symbol. Each chunk is then encoded as an index into the dictionary together with the new symbol. The encoding thus has fixed length, but the chunks vary in length.

---
Tags: coding-theory
---


# Question
Title: Average case complexity of bubble sort vs insertion sort
This site already has some questions on this topic but I am confused after reading some of the answers.

Evaluating the average time complexity of a given bubblesort algorithm.

In the above link, answer by "Joe" says that number of swaps in bubble sort on average is same as number of inversions on average which is (n)(n-1) / 4.

However, https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms says that in bubble sort average number of swaps is $n^2 / 2$ and in insertion sort it is $n^2 /4$ and that's the reason for insertion sort being better than bubble sort.

Which one is correct? Can someone please help me?

# Answer
There is a big difference between the first answer you quote, on this site, and the second answer you quote, on stackoverflow: while the answer on cs.se contains an argument, the answer on stackoverflow just states the result without any explanation. This means that you can *verify* the answer on cs.se: you can check whether the proof is correct, and whether the result answers your question. In contrast, there is no way to know whether the answer on stackoverflow is correct or not, apart from trusting its poster.

This highlights a general difference between *programmers* and *computer scientists*. Programmers just want to know the answer, and generally don't care whether it's correct or not. Computer scientists, in contrast, want to see some evidence: a proof if one is available, or results of experiments (or both, in some communities).

Two more proofs of the formula $\frac{n(n-1)}{4}$ can be found on math.se and on cs.se. See if any of these convince you of this formula. You have to check both the *statement* (whether you are counting the correct expectation) and the *proof*.

Another thing you can do is experimentally determine the veracity of these proofs. This would entail programming both algorithms, and running them on many different arrays of length $n$ for various values of $n$, thus estimating the number of swaps.

A user on stackoverflow did a simpler experiment which suggests that the number of swaps is the *same* in bubble sort and inversion sort (at least for the user's version of these algorithms, quoted in the question). This would imply, of course, that the average number of swaps is the same in both algorithms.
> 2 votes

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


# Question
Title: Size of neighborhood in local search for symmetric TSP
I read about local search / neighborhood search methods for the symmetric TSP and I'm not quite sure about a few things. The given example said:

> Suppose we have an instance of the symmetric TSP with n nodes and the neighborhood $N^k$. Here $N^k$ is the $k$-change-neighborhood (delete $k$ edges and afterwards insert $k$ other edges).

We define $\gamma\_{n, k}$ to be the number of possibilities to delete $k$ non-adjacent edges in a given tour.

If I understand this correctly, it should be as follows: $\gamma\_{n, 0} = 1$, $\gamma\_{n,1} = n$, $\gamma\_{n, 2} = n(n - 3)$, and so on.

> Is there a formula for $\gamma\_{n,k}$?

# Answer
Let $\delta\_{n,k}$ be the number of ways to select $k$ nonadjacent edges on a path of length $n$. We can compute $\delta\_{n,k}$ using a simple recurrence:

* $\delta\_{n,0} = 1$.
* $\delta\_{0,k} = 0$ for $k \> 0$.
* $\delta\_{n,k} = \delta\_{n-1,k} + \delta\_{n-2,k-1}$, where the first term corresponds to the case in which the first edge is chosen, and the other to the case in which the first edge is not chosen.

We can solve this recurrence and obtain $\delta\_{n,k} = \binom{n-k+1}{k}$. Indeed, this satisfies the two base cases, and the inductive case is just Pascal's identity $\binom{n-k+1}{k} = \binom{n-k}{k} + \binom{n-k}{k-1}$.

To compute $\gamma\_{n,k}$, choose a first edge arbitrarily. If it is chosen, we are left with a choice of $k-1$ edges in a path of length $n-3$, and otherwise we are left with a choice of $k$ edges in a path of length $n-1$. In other words, $$ \gamma\_{n,k} = \delta\_{n-1,k} + \delta\_{n-3,k-1} = \binom{n-k}{k} + \binom{n-k-1}{k-1}. $$ This gives $$ \begin{align\*} \gamma\_{n,0} &= 1, \\ \gamma\_{n,1} &= \binom{n-1}{1} + \binom{n-2}{0} = (n-1) + 1 = n, \\ \gamma\_{n,2} &= \binom{n-2}{2} + \binom{n-3}{1} = \frac{(n-2)(n-3)}{2} + (n-3) = \frac{n(n-3)}{2}, \end{align\*} $$ and so on. Note that there is a difference in normalization: you count the edges with order, and I count them without order. This explains the factor of 2 in $\gamma\_{n,2}$. In general, to take the order into account you need to multiply $\gamma\_{n,k}$ by $k!$.
> 1 votes

---
Tags: optimization, traveling-salesman
---