# Question
Title: Examples of NP Complete key exchange algorithms
There's a number of questions on the internet (this site and others; e.g. Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? ) discussing NP hardness of different asymmetric cryptosystems. How well established are NP hard key-sharing systems? That is, systems for establishing a shared key (that can then by used in symmetric encryption) that are based on problems that are known to be NP hard.

I was prompted to this question upon reading about https://en.wikipedia.org/wiki/Anshel-Anshel-Goldfeld\_key\_exchange and wondering if it could be shown to be NP complete when implemented on $GL\_n(F\_2)$ or $GL\_n(\mathbb{R})$, cause these look like awfully hard constraint-satisfaction or quadratic optimization problems at a first glance. The corresponding problem this is based on is the Simultaneous Conjugacy Problem.

I'm aware that there is an important distinction between problems that are merely NP hard in the worst case -- but easy on most random instances, as opposed to problems that are "average-case NP" -- given a set of random instances, solving half of them is still hard. I'd be interested in hearing about key-sharing systems that rely on either notion of hardness.

# Answer
There are *no* known public-key cryptographic algorithms that have been proven to be NP-hard to break. None. So we can't provide you examples, because none are known.

---

Answer to your original question:

The analysis at Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? also applies to public-key exchange.

Cryptography requires average-case hardness. NP-hardness relates to worst-case hardness; it has no notion of a distribution on inputs, probability, or any kind of "average". Worst-case hardness does not appear to imply average-case hardness: there are many problems that are believed to be hard in the worst case, but easy in the average case. Status of Impagliazzo's Worlds? has some pointers on this topic.
> 6 votes

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


# Question
Title: What would a formal grammar for a binary file format look like?
Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive.

What would a context-sensitve grammar for a simple binary format look like?

For example, let's consider a length-prefixed array with the following layout:

```
64 bits | [size * 8] bits
size    | data

```

I suppose the language that corresponds to this format would be:

$$n b^n \\ n \in \[0, 2^{64}\[ \\ b \in \[0, 2^8\[$$

Left-context-sensitive grammars have the following structure:

$$\alpha A \rightarrow \alpha \gamma$$

I don't understand how this formalism could generate or be used to parse a language which contains part of the grammar itself in it. Does the following grammar make any sense?

\begin{align} Bit & \rightarrow 0 \\ Bit & \rightarrow 1 \\ Octet & \rightarrow Bit^8 \\ Size & \rightarrow Octet^8 \\ Size \\; Data & \rightarrow Size \\; Octet^{Size} \\ Array\_s & \rightarrow Size \\; Data \\ \end{align}

I reason that the grammar above matches the structure of left-context-sensitive grammars. It seems clear to me that the next-to-last line of the grammar directly corresponds to the definition above:

\begin{align} \alpha & = Size \\ A & = Data \\ \gamma & = Octet^{Size} \\ \end{align}

The trickiest non-terminal seems to be $Size$. It is not clear to me exactly *how* it influences the grammar's semantics. It is simultaneously part of the input and the grammar, serving as the number of repetitions for $Octet$.

---

I have seen many grammar-based approaches to parsing binary file formats. They include formalisms such as attribute grammars,\[1\]\[2\] adaptive grammars, the recently introduced data-dependent grammars,\[1\]\[2\] parser combinators \[1\]\[2\]\[3\]\[4\]\[5\] and even scattered context grammars.\[1\]

All these tools go beyond the definition above, so I keep wondering about the nature of binary file formats. If it is not possible to describe their language with a context-sensitive grammar, does that mean they are more powerful in the Chomsky hierarchy?

# Answer
1. The Chomsky hierarchy is a hierarchy of grammars described by a given formalism. The other grammar descriptions that you are giving (attribute grammars, ...) are not part of that formalism so they are outside the Chomsky hierarchy (and if I'm not mistaken are able to recognize some languages of higher level in the hierarchy while being unable to recognize other languages at a lower level).
2. Context-sensitive grammars are not at the top of the Chomsky hierarchy, unrestricted grammars are.
3. Context-sensitive grammars can generate what you are asking for, but it's painful to write. Here is a grammar which generate a `s` followed by a binary number, followed by as many `p` as determined by the binary number.

\begin{align} S & \rightarrow \text{s} \\; C \\ \text{s} \\; C & \rightarrow A \\ \text{s} \\; C & \rightarrow \text{s} \\; B \\; \text{p} \\ \text{s} \\; C & \rightarrow \text{s} \\; B \\; C \\; \text{p} \\ A \\; C & \rightarrow A \\; D \\ A \\; D & \rightarrow B \\; D \\ B \\; D & \rightarrow B \\; \text{p} \\ B \\; D & \rightarrow B \\; C \\; \text{p} \\ B \\; C & \rightarrow B \\; E \\ B \\; E & \rightarrow X \\; E \\ X \\; E & \rightarrow X \\; \text{p} \\ X \\; E & \rightarrow X \\; C \\; \text{p} \\ A \\; X & \rightarrow A \\; F \\ A \\; F & \rightarrow B \\; F \\ B \\; F & \rightarrow B \\; A \\ B \\; X & \rightarrow B \\; G \\ B \\; G & \rightarrow X \\; G \\ X \\; G & \rightarrow X \\; A \\ \text{s} \\; X & \rightarrow \text{s} \\; B \\; A \\ A & \rightarrow 0 \\ B & \rightarrow 1 \\ \end{align}

Yes that's a lot of rules (I may have missed some shortcuts, but on the other hand I may have missed some cases where unwanted strings are generated which could be avoided only with a more complex grammar). Some explanations:

* I'm using $A$ and $B$ for temporary place holder for $0$ and $1$ because context sensitive rules do not allow to modify terminals. The last two rules replace them by the terminals they were acting for.
* the first three rules are pretty obvious.
* the fourth is starting the count
* the next four are transforming a count ending by a $0$ in a count ending by a $1$ and a $\text{p}$
* the next four are transforming a count ending by a $1$ in a count ending by a $X$ (meaning a carry to be propagated) and a $\text{p}$
* the last seven rules are doing the carry propagation.
> 3 votes

---
Tags: formal-languages, formal-grammars, parsers, context-sensitive, information-retrieval
---


# Question
Title: Many-one reducibility: why $A = \{1\}$ is not a counterexample to $\forall A : A \leq_m A \cup \{0\}$?
I'm looking at a textbook exercise that asks to prove or give a counterexample that $\forall A : A \leq\_m A \cup \\{0\\}$.

$A \leq\_m B$ is defined as:

$\exists f$ total, computable s.t. $\forall x \in A : x \in A \Leftrightarrow f(x) \in B$,

It then says in the answer sheet something to the effect of:

> The *only* counterexample is $A = \mathbb{N} \setminus \\{ 0 \\}$.
>
> Otherwise there is always an appropriate $f$:
>
> 1. If $0 \in A$, $id$ is good enough
> 2. If $0 \not\in A$, one such $f$ is
>
> $f'(x) = \begin{cases} x\_0 & x = 0\\ x & otherwise\end{cases} $ for some $x\_0 \not\in A \cup \\{0\\}$.

However, before checking the answer sheet I was persuaded there were multiple such counterexamples.

In fact, I still don't understand what's wrong in my "proof" that $A = \\{ 1\\}$ is a counterexample.

It goes like this:

> Let $A = \\{1\\}$. Then $A \cup \\{0\\} = \\{0,1\\}$. Suppose such an $f$ as required by the definition exists.
>
> There are three cases, mutually exclusive by definition of function:
>
> 1. $(1,0) \in f$, therefore $f(A) = \\{0\\} \neq A \cup \\{0\\} = \\{0,1\\}$
> 2. $(1,1) \in f$, therefore $f(A) = \\{1\\} \neq A \cup \\{0\\} = \\{0,1\\}$
> 3. $(1,c) \in f$ for some other $c$, therefore $f(A) = \\{c\\} \neq A \cup \\{0\\} = \\{0,1\\}$
>
> Therefore $f$ such that $f(A) = A \cup \\{0\\}$ cannot exist for $A = \\{ 1 \\}$. QED.

In particular, I don't see how, for the given

$f'(x) = \begin{cases} x\_0 & x = 0\\ x & otherwise\end{cases} $

it holds that $f'(\\{1\\}) = \\{1,0\\}$

It seems to me that $f'(\\{1\\}) = \\{1\\} \neq \\{0,1\\}$.

What am I misunderstanding about either basic set theory or the definition of $\leq\_m$?

# Answer
> 2 votes
The property that, for all $x$, $x\in A$ iff $f(x)\in B$ means that $f(A)\subseteq B$ and $f(\overline{A})\subseteq \overline{B}$. Your proof attempt uses the condition $f(A)=B$, which is neither necessary nor sufficient.

---
Tags: computability, reductions, sets
---


# Question
Title: Understanding compression/encoding in linear time
I'm reading the paper N. J. Larsson, A. Moffat: Offline Dictionary-Based Compression, which describes a compression algorithm that, if I understand it correctly, is quite similar to Byte pair encoding.

Given a string $S$ of length $n$, I'm trying to understand how one can compress it in linear, $\mathcal O (n)$, time with this compression method. How exactly is this done? I've read the paper, but I still don't understand how they achieve linear time, so maybe I would understand it explained in a different way.

My first confusion arises in the first step in the algorithm, where we find the most common pair, e.g. in `abcababcabc` the most common pair `ab` would be replaced by a new symbol, say `XcXXcXc`. I don't understand how we can find the most common pair quickly enough. My naive approach would be to look first at the first pair `ab` and then count the number of occurrences, then look at the next pair `bc` and count the number of occurrences, etc. However this would already give $\mathcal O (n^2)$ just for finding the most common pair *once*.

Next, even if I understood how to find the most common pair in $\mathcal O(n)$ time. My next problem is that, don't we have to find the most common pair up to $\mathcal O(n)$ times? And hence this would give a total time of $\mathcal O(n^2)$?

# Answer
I have checked the code, reread the paper and it seems that algorithm is not performing in $\mathcal O(n)$ in the way you have described.
The recursive calls of finding pairs works in $\mathcal O(n \log n)$ divided by constant if you wish to pack it to the end. In fact the structure underneath keeps pointers to the first occurence of pair, splits the queue of pairs by occurences to make it efficient, but still loglinear. On the other hand by analysing the code written by Ph.D. student of the author I have discovered several tricks - the length of pairs (the original name) is given as parameter (default is 2) and the recurrence is limited by parameter, which can discard further calls (default is about 5 levels), with ability to make only one pass or push to the end. The default code runs in $\mathcal O(n)$, but will not yield optimal compression. There is also switch to prefer memory, time or be neutral.

The paper and the code shows usage of hash-table, which runs only in expected constant time, but the function given works very well with characters. Also the code limits the input length by constant hardcoded.

Changing hashtable to suffix tree and rewritting the part of recurrence into bookkeepping partial pairs might yield better results - I am not sure if this is possible to make it $\mathcal O(n)$, this would be probably a different question.

There is also trick used to keep empty space from traversing - the start of empty block points to the first non-empty character, but this only speeds up traversing, still with loglinear time. The part responsible for this behaviour is replacing pairs by the new character every iteration - keeping only rewrite rules and operating on them would be faster, but still the access to check if new *pairs* were introduced would require to check rewrite rules against the new ones - in the case we build full binary tree with pairs at the leaves in such way that after replacing pair with new character and concating with the parent we got new pairs at the leaves up to the root - there are $n$ chatacters then $\frac{n}{2}$ pairs, then $\frac{n}{4}$, $\frac{n}{8}$, $\frac{n}{16}$... You see the pattern, there are $2n$ pairs, but according to algorithm description this yelds $\mathcal O(n\log n + n)$ time taking only input traversals.
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, data-compression, encoding-scheme
---


# Question
Title: What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content?
I have two large files containing paragraphs of English text:

1. The first text is about 200 pages long and has about 10 paragraphs per page (each paragraph is 5 sentences long).
2. The second text contains almost precisely the same paragraphs and text as the first. It is also 200 pages long with 10 paragraphs per page. However, the paragraphs are randomized and in a different order when compared to the first text. Also, a large percentage of the paragraphs have small changes in wording compared to similar paragraphs. For example, a paragraph in the first text might have a sentence like `Like Jimmy, I wanted to go to the palace` while the corresponding sentence in the paragraph of the second text would read `Like Jimmy, I really wanted to go to the castle`.

I want to be able to capture the changes here like the addition of `really` and the deletion of `palace` with replacement of `castle`. If the paragraphs were roughly aligned, then this would be pretty trivial as there are plenty of ways to diff text. However, since the paragraphs aren't aligned, that isn't the case.

If the files were small (handful of paragraphs), Levenshtein Distance probably would work fine, but because the files are huge, it would be inefficient to compare each paragraph of text 1 to each paragraph of text 2 to find out which paragraphs match.

What would be some other approaches to this problem to handle it efficiently?

# Answer
> 1 votes
Comparing 2000 paragraphs to 2000 paragraphs is only four million comparisons.

The key to the problem is **not** to use a function that computes the Levenshtein distance but to use one that computes the Levenshtein distance *if the distance is less than a certain threshold*, and fails (or, rather, returns +∞) if the distance is greater than the threshold.

This is because you are only interested in closely similar paragraphs. You have no interest at all in the *precise* distance between paragraphs that are different enough to be unrelated. So as soon as a distance has got high enough to be uninteresting, the function can exit at once; and this will mostly happen very early on indeed during the execution of the function.

The higher the threshold, the longer the running time but the smaller the proportion of false negatives.

If you know something more about the documents (such as that each paragraph matches at most one paragraph in the other document) then you could make one pass with a low threshold, exclude the matched paragraphs from further consideration, make one pass over your now reduced corpus with a higher threshold, exclude *those* reduced paragraphs, and so on.

*Implementation detail:* Presumably you would be calculating a Levenshtein distance on words rather than on characters. If that is the case, you should first assign a number to each word - for example, by sorting the entire corpus, calling the first word '1', the second word '2', and so on. That way your paragraph comparisons would be done by comparing numbers rather than words, which is faster.

# Answer
> -1 votes
It might be possible to use a compound approach. Perhaps someone can build on this...

Hash the contents of the paragraph in such a way that paragraphs with only slight differences have similar hashes, then order the hashes to determine which paragraphs to compare via a more exact method (diff or something similar).

For example, as a rudimentary hash algorithm, what if you added up the ascii values of the characters and then modulo the sum by a large number like 2,000,000,000? This would cause 2 paragraphs with only a few added or subtracted words to have hash values that are likely closer together than paragraphs with very different words, and thus, they will be much closer together on the list than the very different paragraphs (you might say nearby hashes in this case are necessary but not sufficient for similar paragraphs). Obviously you have to account for the wrap-around caused by modulo and consider a paragraph with the hash value 1,999,999,999 as only being a distance of 1 from one with a has value of 0, etc.

As a result, could reduce the number of comparisons between paragraphs that you need to perform by a substantial amount (you wouldn't have to compare each paragraph in one text to every paragraph in the other text) -- you could compare a paragraph to paragraphs in text 2 in order of how close their hashes are (do the closest hash-valued ones first) and invoke a more expensive algorithm here to determine if they're "similar enough" to be considered the same.

---
Tags: strings, data-mining, natural-language-processing, edit-distance
---


# Question
Title: When do the gradients exist in a Reinforcement Learning setting?
I am getting properly stuck into reinforcement learning and I am currently reading the review paper by Kober et al. (2013).

And there is one constant feature that I cannot get my head around, but which is mentioned a lot, not just in this paper, but others too; namely the existence of gradients.

In section 2.2.2. they say:

> The approach is very straightforward and even applicable to policies that are not differentiable.

w.r.t. to *finite difference gradients*.

What does it mean to say that the gradients exist and indeed, how do we know that they exist? When wouldn't they exist?

# Answer
> 2 votes
The gradient doesn't exist / isn't well-defined for non-differentiable functions. What they mean by that statement is that there is an *analogous* version of gradients that can be used, instead of the gradient.

## Discrete functions

In the discrete case, finite differences are the discrete version of derivatives. The derivative of a single-variable continuous function $f:\mathbb{R} \to \mathbb{R}$ is $df/dx$; the partial difference (a discrete derivative) of a single-variable discrete function $g:\mathbb{Z} \to \mathbb{Z}$ is $\Delta f : \mathbb{Z} \to \mathbb{Z}$ given by

$$\Delta f(x) = f(x+1)-f(x).$$

There's a similar thing that's analogous to a gradient. If we have a function $f(x,y)$ of two variables, the gradient consists of partial derivatives $\partial f / \partial x$ and $\partial f / \partial y$. In the discrete case $g(x,y)$, we have partial differences $\Delta\_x f$ and $\Delta\_y f$, where

$$\Delta\_x f(x,y) = f(x+1,y) - f(x)$$

and similarly for $\Delta\_y f$.

## Continuous functions

If you have a continuous function that is not differentiable at some points (so the gradient does not exist), sometimes you can use the subgradient in lieu of the gradient.

---
Tags: reinforcement-learning
---


# Question
Title: Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?
One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there algorithms that are intended exactly for finding power of matrix and that are more efficient than sequential execution of matrix multiplication? I am particularly interested in parallel algorithms.

# Answer
If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate:

Stage 1: Calculate $M^2$

Stage 2: Calculate $M^3 = M^2 * M$ and $M^4 = M^2 * M^2$

Stage 3: Calculate $M^7 = M^4 * M^3$ and $M^8 = M^4 * M^4$

Stage 4: Calculate $M^{15} = M^8 * M^7$

This is one multiplication more than calculating $M^5$ in three multiplications and raising $M^5$ to the third power in another two multiplications, but should be faster if you have two processors. For arbitrary high powers, you will need more processors.

If you use a brute force algorithm for the multiplication, multiplying row by column, you may save some time by calculating one row of a product, then immediately using that row for the next product. This would help in the calculation of $M^3$ where we can start calculating $M^3$ as soon as the first row of $M^2$ has been calculated; it wouldn't be that helpful with $M^4$ since we need both rows and columns of $M^2$. For large powers, you could probably arrange which powers to calculate.

And after posting this it becomes obvious that you can use multiple processors very easily: You start by calculating the first row of $M^2 = M * M$. When you have that row, you have all the information you need to calculate the first row of $M^3 = M^2 * M$, so you calculate the second row of $M^2$ and the first row of $M^3$ in parallel. Then you can calculate the third row of $M^2$, the second row of $M^3$, and the first row of $M^4$ in parallel and so on.

This will do a lot more operations than necessary (for example, 14 matrix multiplications for $M^{15}$ instead of the minimal 5 or the 6 of the four-stage method). If the power is not large compared to the number of processors this will still be faster. But calculating $M^{1000}$ with four processors using this method will be inefficient; doing this in an optimal way would be an interesting problem.

Combining approaches: Using four processors for example, you can calculate AB, ABC, ABCD and ABCDE almost in parallel by calculating each product one row at a time. This allows calculate all four of $M^2$ to $M^5$ using four processors in about the same time as one product with one processor.

Given these four results and the original M, you can calculate four of the matrices $M^6$ to $M^{25}$ in the same time again, provided the matrices are at most five powers apart from each other. So each power up to $M^{25}$ can be calculated in about twice the time of a single processor matrix product.

With these matrices calculated, all matrices up to $M^{108}$ and some more up to $M^{125}$ can be calculated in three times the time of a single matrix product if four processors are available. With k processors this should go up to at least the power $k (k+1)^2$.
> 5 votes

# Answer
There's two levels you can analyze parallel speedups with matrix exponentiation: The "macro-algorithmic" level that decides which matrices to multiply, and the "micro-algorithmic" level where you can speed up the multiplications themselves with parallelism.

For the latter, Wikipedia suggests that for multiplying an $n$ by $n$ matrix, we can achieve a complexity of $O(\log^2(n))$ theoretically with an unbounded number of processors, or $O(n)$ with a more realistic parallel algorithm.

(Note: the wikipedia page is for general matrix computation. I'm not sure if that can be parallelized even further using the information that we are squaring a matrix.)

For the former, the question turns into how many rounds of matrix multiplication are necessary to compute $A^m$ for some matrix $A$? (I say rounds, because all the multiplications in a given round may be done in parallel).

The sequential algorithm to beat, as noted in other answers, is Exponentiation by squaring. This allows you to compute $A^k$ in $O(\log(k))$ multiplications.

The question is: can we beat this with parallelism? I claim the answer is no.

The simple reason is that exponentiation by squaring is essentially a dynamic programming algorithm; it lets you skip all the work by reusing subresults, but this in turn creates a data dependency that disallows parallelism. If we get rid of the data dependency, but we also vastly increase the amount of work we have to do.

To better illustrate this, let's look at how you would parallelize matrix multiplication if we were not doing exponentiation. Suppose you were looking to parallelize multiplying $k$ *separate* square matrices:

$$A\_1 A\_2 A\_3 A\_4 A\_5 ... A\_k$$

The natural way to parallelize this is obvious, you should abuse associativity to perform $\frac{k}{2}$ multiplications in the first round:

$$(A\_1 A\_2)(A\_3 A\_4)(A\_5 A\_6) ... (A\_{k-1}A\_k)$$

From this, we can clearly multiply our $k$ matrices in $O(\log(k))$ rounds of multiplication because we reduce our problem size by half each round.

However, if we were to perform exponentiation this way, it would look like this:

$$(A A)(A A)(A A)...(A A)$$

In other words, all our parallelism is gaining us is recomputing the same matrix product to calculate $A^2$! Thus,if we use a memoized algorithm such as Exponentiation by squaring, we can do the same thing as the parallel algorithm at each *round* of multiplication.

Putting all this together, if we want to calculate $A^k$ for $n$ by $n$ matrix $A$, the parallel complexity is $O(\log^2(n)\log(k))$ for the optimistic parallel algorithm, or $O(n\log(k))$ for the realistic one.
> 4 votes

# Answer
If by sequential you mean multiplying $m$ times, the $\log m$ solution of initially only calculating the relevant powers of $2$ (a.k.a Exponentiation by squaring) is clearly better for large $m$.

Improving on that may be specific to certain types of matrices. For instance, if your matrix is diagonalizable, $$A = S \Lambda S^{-1} \rightarrow A^m = S \Lambda^m S^{-1}$$ Thus, calculating the $m$th power is $O(1)$ in $m$.
> 3 votes

---
Tags: algorithms, parallel-computing, efficiency, matrices, numerical-algorithms
---


# Question
Title: Reference request: Introduction to reinforcement learning with hand calculation examples
For me, the most difficulty when it comes to learning about reinforcement learning is that there is not much to learn in the sense that without running some algorithm, it is very difficult to get a sense of how abstract RL framework is done in practice.

This is in contrast to a lot of the stuff you learn in related courses on optimization, game theory or even pure algorithm. In each of these courses, you have a large amount of examples where you can hand compute to obtain the solution (for algorithms, you can solve for shortest path etc by hand). It is also easy to compute the gradient, and calculate the value at each step using gradient descent algorithm for example in an optimization class, or compute the Nash equilibria in simple games. This allows one to better appreciate how the algorithms work.

Even for supervised machine learning, algorithms such as ANN, KNN, SVM etc. can be analyzed by hand, using step by step calculation. However, this does not seem to be the case for reinforcement learning. Every article I have came across basically runs through the whole "state, action, reward" framework then goes on talking about MDP and Q, TD learning. Then applications that usually follows are not something that are easily programmed on a first try i.e. robotic acrobat, pole cart system etc.

**Are there any introduction or tutorial to reinforcement learning where a problem is solved by hand?** Meaning, you can actually compute the values at each step following a particular technique and perhaps obtain the optimal solution.

Even if not, are there any mathematical convergence analysis of reinforcement learning algorithms?

# Answer
> 2 votes
Poole and Mackworth's *Artificial Intelligence: Foundations of Computational Agents*, fully available online, has one such example for Q-learning.

Sutton & Barto's *Reinforcement Learning: An Introduction*, also online, has a few tiny iterative examples here and there.

Isbell & Littman's udacity course on RL has examples, quizzes, and programming exercises in Java.

---
Tags: optimization, reference-request, machine-learning, mathematical-analysis, reinforcement-learning
---


# Question
Title: Has the notion of "non-cheating" quines been formalised?
Informally, it is often said that some quines "cheat", such as those that read their own source code from memory, or the case where a program consisting of the empty string happens to output the empty string.

Quines that are considerd to be "non-cheating" always seem to have the same structure. There is some data structure (usually, but not always, a string) which contains some representation of the source code. This structure is read twice, once to reformat it into the code part of the final output, and a second time where it's copied verbatim to reproduce the data part. For example, the following Python example (which I just invented) has this structure:

```
x = """x = {0}{1}{0}
print x.format(chr(34)*3,x)"""
print x.format(chr(34)*3,x)

```

The string 'x' is referred to twice in the last line, once to reformat it, and a second time to paste it verbatim into the reformatted string.

My question is whether this notion of "cheating" or "non-cheating" quines has been, or can be, formalised. That is to say, if we are given a formal specification of a language and its semantics, and we are also given an example of a quine in that language, is there a well-defined way to say, in principle, whether that quine is "cheating" or not? Or is this notion of "cheating" inherently too vague to admit a formal definition?

If this notion can be formally defined, is it possible to have a language that only admits "non-cheating" quines, and is an example of such a language known?

# Answer
Most formal semantics for programing languages tend to keep things simple, in particular, it's pretty rare to have the ability to express "grabbing your own source code" in a formal semantics.

This has the somewhat dubious advantage of disallowing some kinds of "cheating" *by construction*: the "cheat" is simply not part of the language semantics. In particular, a simple lambda calculus with simple string concatenation and printing primitives cannot implement many (any?) of the "cheats" you have in mind. In such a language, a quine might be a program which prints the exact string representation of it's own code. You can even avoid the `print` primitive if you allow returning the string rather than printing it. In that case, you only need string literals and concatenation.

It's a useful exercise to figure out various properties of quines in such a language. It's pretty easy to see that some variable will need to be repeated twice: there are no "linear" quines. However the statement

> This structure is read twice, once to reformat it into the code part of the final output, and a second time where it's copied verbatim to reproduce the data part.

is a bit vague, and I'm not sure it's true in general, depending on the precise meaning of "copied verbatim".
> 2 votes

---
Tags: formal-languages
---


title: Can Tree Transducers Self-Interpret?

text:
# Question
Title: Can Tree Transducers Self-Interpret?
Is it possible for MSO graph/tree transducers to reflect themselves, namely to create an interpreter of tree/graph transducers using tree/graph transducers? If yes, I'll be happy for some design guidelines.

# Answer
> 2 votes
Not in any straightforward way, because a tree transducer only accepts a single input, while an interpreter needs two inputs.

An interpreter needs *two* inputs: a transducer $R$ and a tree $T$, and would output the $R(T)$. But a tree transducer can only accept *one* input.

Consequently, there appears to be no way to build such an interpreter (unless you accept some crazy way of pre-processing the inputs to bring them into a form that they can be provided to a tree transducer -- but it's hard to see how to define that in a way that rules out trivial solutions where it's the pre-processor that's actually doing all the interpreting).

---
Tags: programming-languages, interpreters, transducers
---


# Question
Title: Check if a given polynomial is primitive
I try to estimate error detection capabilities of arbitrary CRC polynomials. One important criteria is if a given polynomial is primitive. So I need an algorithm to check that. My goal is to write a C or C++ routine.

Unfortunately I only found analytical solutions for the problem on the web.

Is there some numerical algorithm for testing a given polynomial for primitivity?

Please consider that my mathematical knowledge wasted away during the last two decades. Any algorithm descriptions, pseudo code or code in a common programming language would be very helpful.

# Answer
In order to check that a degree $n$ polynomial $P$ over $GF(2)$ is primitive, you first need to know the factorization of $2^n-1$ (you can look it up in tables, or use a CAS). Then, you test that $x^{2^n-1} \equiv 1 \pmod{P(x)}$ (using repeated squaring to do this efficiently), and that for every prime factor $p$ of $2^n-1$, $x^{(2^n-1)/p} \not\equiv 1 \pmod{P(x)}$.

You can also just use a CAS (computer algebra software). For example, using the free software Sage you can do

```
F.<x> = GF(2)[]
(x^8+x^6+x^5+x+1).is_primitive()

```

For more on the relevant mathematics, see the Wikipedia article.
> 6 votes

---
Tags: numerical-algorithms, polynomials, crc
---


# Question
Title: What is an efficient way to calculate the biggest system of disjunct sets?
Let $I$ be a finite set of items and $\mathcal{M} = \\{M | M \subseteq I\\}$ be a set of subsets of $I$.

The task is to find the biggest subset $\tilde{\mathcal{M}} \subseteq \mathcal{M}$ so that all elements of $\tilde{\mathcal{M}}$ are pairwise disjoint:

$$\text{arg } \max\_{\tilde{\mathcal{M}} \subseteq \mathcal{M}} |\tilde{\mathcal{M}}| \text{ with } \bigcap\_{M \in \tilde{\mathcal{M}}} M = \emptyset$$

What is an efficient algorithm to do so?

(If $|I| \approx 10\\,000$ and $|\mathcal{M}| \approx 100$ )

## Example

Let $I = \\{a, b, c, d, e\\}$ be the set of items and

$$\mathcal{M} = \\{A, B, C, D\\}$$

with

$$ \begin{align} A &= \\{a\\}\\ B &= \\{b, c\\}\\ C &= \\{a, c\\}\\ D &= \\{b, d\\} \end{align} $$

Then $$\tilde{\mathcal{M}} = \\{A, B\\}$$ is one of the solutions. There is no way to have $|\tilde{\mathcal{M}}| \geq 3$.

## Ideas

### Brute force

```
M_tilde_max = None
for Mc_tilde in powerset(Mc):
    if Mc_tilde is disjunct and (M_tilde_max is None or M_tilde_max < |Mc_tilde|):
        M_tilde_max = Mc_tilde

```

This has complexity $\mathcal{O}(2^{|\mathcal{M}|})$.

### Apriori

If a set $\tilde{\mathcal{M}}$ has only disjunct items, then all possible subsets have to be disjunct. So one can at first find all sets of size 1 which have this property (which are simply all sets), then all sets of size two, then all of size 3, ...

This has the same worst-case time complexity as brute force as in the worst case $\tilde{\mathcal{M}}$ is just equal to $\mathcal{M}$. It might in some scenarios - if one knows that it will be smaller - be much better. However, the space complexity is quite bad here.

### More

I guess one could pre-compute for all $|\mathcal{M}|^2$ combinations of two sets if they are disjunct or not. After that, the table can be used and $\mathcal{M}$ and $I$ don't have to be touched at all. This is the maximum satisfiability problem. Each set $M\_i \in \mathcal{M}$ is a boolean variable $x\_i$. If $M\_i$ and $M\_j$ are disjunct, then $(x\_i \lor x\_j)$ is added. If not, then either $(x\_i \lor \neg x\_j)$ or $(\neg x\_i \lor x\_j)$ can be added (I think it doesn't matter which one?). This way, a conjunctive normal form can be produced. All clauses have only two elements, so I think there might be an efficient algorithm for it?

## Context

This question is more a brain-teaser for me. It started with the following problem:

I would like to generate a tree of categories for Wikimedia commons. The problem is that categories in Wikimedia Commons are not disjunct. For example, for https://commons.wikimedia.org/wiki/Category:Rosa there is the category "Roses by location", "Rosa by month", "Roses by photographer" which are not what I want. However, to filter those I think just removing categories with the substring " by " might be enough. I have to check it, though.

# Answer
This answer assumes that the sets in $\tilde{\mathcal{M}}$ have to be pairwise disjoint (as currently stated, you are requiring them to have empty intersection, which is a monotone condition).

The decision version of your problem is NP-complete, by reduction from independent set. Given an graph $G = (V,E)$, construct a set system with a set $S\_x$ for each vertex $x \in V$, and an element $e$ for each edge $e \in E$. The set $S\_x$ contains all edges incident to $x$. A family of sets is pairwise disjoint iff the corresponding vertices form an independent set.

We can also go in the other direction, following one of your suggestions. Given a set system, construct a graph in which each vertex corresponds to a set, and two vertices are connected if the sets intersect. A solution to your problem is the same as an independent set in the graph.
> 4 votes

---
Tags: algorithms, satisfiability, sets
---


# Question
Title: Minimal requirements for Kleene's recursion theorem
Kleene's recursion theorem guarantees that any Turing complete language must have quines. However, consider the following quine (in C, taken from the Quine page):

```
 char*f="char*f=%c%s%c;main()
 {printf(f,34,f,34,10);}%c";
 main(){printf(f,34,f,34,10);}

```

It makes no use of `while` or recursive functions, or any other of the features that make C Turing complete. It would work just fine in a subset of C that included only `printf` and basic string manipulations.

This makes me wonder whether Turing completeness is really necessary for the proof of Kleene's recursion theorem. Does the proof actually require it? If not, what is the most general class of languages to which the theorem applies?

Note that I'm not asking for the most general class of languages that have quines (which would be rather trivial), but the most general class of languages that have quines *because of Kleene's recursion theorem*. That is, I'm asking for the minimal set of language features needed to implement the recursion trick that's used in the most conservative proof of the theorem, thus guaranteeing that all languages within that class must have quines. Presumably the set of all languages that implement these features will be a subset of the set of all languages that exhibit quines, but it might be a superset of the Turing complete languages.

The Wikipedia page hints at this with the following text:

> However, a direct proof of Kleene's theorem (Kleene 1952: p. 352-353) does not make use of a universal program, which means that the theorem holds for certain subrecursive programming systems that do not have a universal program.

I don't currently have access to that reference, and I would like to know precisely which set of "subrecursive programming systems" this is referring to.

# Answer
I stumbled upon a (partial) answer myself, in David Madore's essay about quines. I quote,

> A different, perhaps more satisfactory, way of stating the fixed-point theorem would be to eliminate the universality theorem from it, and to say: for every computable function $k$ there exists a $n$ such that $\phi\_n(\dots) = k(n\dots)$. This corresponds more precisely to the intuitive content we have described. It is proved *without* the use of the universality theorem, using only the s-m-n theorem (for the actual proof, take the proof we have just given, and replace $\phi\_{h(x)}(\dots)$ by $k(x\dots)$ everywhere). The advantage of formulating things like this is we see that it also works for primitive recursive functions (which satisfy s-m-n but not universality), so in effect a primitive recursive function can also make use of its own number. By applying the universality theorem (the function $\phi\_{h(x)}(\dots)$ is computable, so we can call it $k(x\dots)$) we recover the fixed-point theorem as we have stated it.

So Kleene's fixed point theorem goes through at least for primitive recursive functions. It might still be that there's an even simpler class of languages that it also applies to, and I won't accept my own answer in case someone else has more to say on that topic. But for now I'm happy knowing this.
> 5 votes

---
Tags: computability
---


# Question
Title: Vehicle Routing Problem Using Simulated Annealing
Suppose I have some locations where goods are to be delivered in multiple time slots(like 7-10 am , 10 am-1 pm, time slots are continuous). All the locations are connected with each other(completely connected graph).

1.) Firstly orders of first slot are to be delivered and then only orders of other slots can be delivered.So, the last point of most optimal first slot sub-tour might not be the most optimal for the overall distance minimization. We might need to go from that last point to some other point of first slot and then from there on go to locations of slot2.

2.) Minimize distance

3.) Trip starts from a depot and ends at the depot( So sequence is something like depot -\> Slot 1 orders -\> Slot 2 orders -\> .......... -\> depot , where slot1 is 7-10 am , slot2 is 10 am - 1 pm, slot3 is 1 pm - 4 pm......).

My question is how can this problem be tackled with simulated annealing. like how to fix the starting and end points(as depot) and how to set annealing schedule for such problem.

# Answer
> 1 votes
To solve a combinatorial optimisation problem such as this by a method such as Simulated Annealing, you need 3 basic ingredients:

1. A representation for a 'Candidate Solution'. For vehicle routing, this is typically a permutation of the depots, i.e. a list of depots in the order to be visited.
2. A measure of the quality of a candidate solution. Various methods exist for penalising solutions with deliveries outside their time windows or fail to meet other constraints.
3. One or more 'perturbation operators' for transforming a candidate solution into another (hopefully better) one. For example, swapping two randomly-chosen depots in the permutation is one of the simplest approaches, but of course more informed operators as possible.

Given these three, it's then possible to plug your problem into a range of metaheuristics, such as iterated local search, Tabu search, various Evolutionary Algorithms or Tabu search.

As regards annealing schedule, there's a range of literate on choosing parameters, but one simple option is to obtain initial and final temperatures from the statistics of a sequence of random perturbations, then experiment with the choice of cooling rate in a geometric annealing schedule.

The excellent (and freely-available) book "Essentials of Metaheuristics" offers a more detailed background on the above and some guidelines for what techniques to apply in what circumstances.

---
Tags: traveling-salesman, weighted-graphs
---


# Question
Title: What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)?
What is the space complexity of function $f(x) = \sum\_{i=1}^x g(i)$ where g(n) is O(n)?

Is it O(n) because the maximum stack size is n, or is it O($n^2$) because there are $n(n+1)/2$ memory references?

# Answer
> 0 votes
Space complexity is about the maximum stack size, so this function uses $O(n)=O(\log(x))$ space. Your intuition about this is right: each call to $g$ uses and overwrites memory previously used by the previous call to $g$, so the stack grows to $O(n)$

Why the $\log(x)$ factor? If $g$ uses $O(n)$ memory for an $n$-bit input, then it uses $O(n)=O(|x|) = O(\log(x))$ memory for input $x$, which is of length $|x|=\log(x)$.

# Answer
> 0 votes
f (x) *can* be calculated with O (x) space. In practice, if you are interested in speed, you would try to find out if calculating g (n) for x different values can be done faster than n individual calculations. You might find a way to calculate f (x) that is significantly faster than adding x values, but takes more space.

An example: Let g (n) be the same of the divisors of n. f (x) can be calculated almost as fast as a single value g (n) in the worst case.

---
Tags: algorithms, space-complexity
---


# Question
Title: Find ellipsoid that contains intersection of an ellipsoid and a hyperplane
I have an $n$-dimensional ellipsoid $E$ and a hyperplane $H$. This hyperplane cuts $E$ into two parts: $E\_1$ and $E\_2$ (whose disjoint union is $E$). I want to find another ellipsoid $E'$ that has minimal hyper-volume and contains $E\_1$. Is there an efficient algorithm to do this?

My first thought was to formulate it as an optimization problem, but I am having difficulty with formulating it, as I don't know how to formulate the containment ($E\_1 \subseteq E'$) constraint.

An approximation for the minimal hyper-volume ellipsoid is also good for my needs.

# Answer
Your are describing the basic step in the ellipsoid algorithm. Your question might be answered in lecture notes on the algorithm, such as these ones by Goemans.

More generally, given a convex body $K$, the minimum volume ellipsoid containing it is called the Löwner–John ellipsoid. The same name is also given to the maximum volume ellipsoid contained in $K$. See for example these lecture notes of Boyd and Vandenberghe.
> 3 votes

---
Tags: optimization, computational-geometry, approximation
---


# Question
Title: Relation between "syntax" and "grammar" in CS
I do sure that "grammar" and "syntax" is two different thing in CS, e.g

> Syntax of Java language is defined by a context-free grammar.

My question are

What is different in definitions of "grammar" and "syntax" in CS?

What is relation between them, can we describe it by using set theory?

# Answer
Your quote has the following operational meaning for *syntax* in the context of programming languages:

> The *syntax* of a programming language is the set of all syntactically valid programs.

The syntax only describes what the valid programs look like; *semantics* gives them meaning – tells you how to execute them.

The set of all valid programs is an example of a formal language; a *formal language* is just a collection of strings. There are many ways of describing formal languages. One of them is through formal grammars, which you can think of as a type of formula that describes a formal language. Context-free grammars are a restricted type of formal grammars. As such, they cannot describe all formal languages, but only context-free languages. (General grammars also describe only some of the formal languages; this is due to the fact that there are countably many grammars but uncountably many formal languages.) Summarizing:

> A *grammar* is one way to specify a formal language.

Finally, let me mention that the set of syntactically valid Java programs actually cannot be described by a context-free grammar; only some features can be described. Context-free grammars cannot enforce, for example, that a variable not be defined twice in the same context. However, once we abstract away such details (for example, by replacing variable names with generic placeholders), the resulting set of syntactically valid Java programs does lend itself (perhaps) to being captured by a context-free grammar.

*Parsing* (in our context) is the process of reading the source code of a Java program and constructing its *parse tree*, which is its structure as seen from the perspective of the context-free grammar. The parse tree captures the semantics of the program in a form amenable to further manipulation in the compilation process. Abstracting away details such as variable names and values of constants relegates this information into the form of *parameters*, but doesn't obstruct the control structure of the program.
> 7 votes

---
Tags: terminology, context-free, formal-grammars, programming-languages, syntax
---


# Question
Title: Sum of size of distinct set of descendants $d$ distance from a node $u$, over all $u$ and $d$ is $\mathcal{O}(n\sqrt{n})$
Let's consider a rooted tree $T$ of $n$ nodes. For any node $u$ of the tree, define $L(u,d)$ to be the list of descendants of $u$ that are distance $d$ away from $u$. Let $|L(u,d)|$ denote the number of nodes that are present in the list $L(u,d)$.

Prove that the sum of $|L(u,d)|$ over all distinct lists $L(u,d)$ is bounded by $\mathcal{O}(n\sqrt{n})$.

# My work

Consider all $L(u,d)$ such that the left most node on the level $Level(u) + d$ is some node $v$. The pairs $u, d$ for all such $L(u,d)$ must be distinct and the sum of all $d\_i$ will correspond to the number of nodes $x$ in the tree with $Level(x) \le Level(u) + d$.

This is because if some sequence of nodes $v\_1, v\_2, \dots v\_k$ corresponds to the descendants of some node $u$ at a distance $d$ and the sequence of nodes $v\_1, v\_2, \dots v\_{k'}$ where $k' \> k$ corresponds to the descendants of some node $u'$ at a distance $d+1$, then there must also exist a node $u''$ such that $L(u'', d) = v\_{k+1}, v\_{k+2}, \dots v\_{k'}$. This would also mean that $u''$ is not in the subtree of $u$ and thus there are at least $d$ distinct nodes in the subtree of $u''$ upto a distance $d$ from $u''$.

If the distinct distances are $d\_1, d\_2, \dots d\_k$ then, $n \ge \sum\_{i}d\_i \ge \sum\_{i=1}^{k}i \ge \frac{k(k+1)}{2}$. =

$\implies k \le \sqrt{n}$

After this I tried to show that there can be only $\mathcal{O}(\sqrt{n})$ distinct lists $L(u,d)$ so that I can then trivially obtain the upper-boud of $n\sqrt{n}$ but I could not make any more useful observations.

This link claims that such an upper bound does exist but has not provided the proof.

Any ideas how we might proceed to prove this?

# Answer
Let us start by giving an alternative formula for $\sum\_{u,d} |L(u,d)|$. For a node $x$, let $\pi^{(d)}(x)$ be its $d$'th parent, and let $h(x)$ be its height. Then $$ \sum\_{u,d} |L(u,d)| = \sum\_x |\\{ L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\\}|. $$ It suffices to show that $|\\{ L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\\}| = O(\sqrt{n})$ for all nodes $x$.

Let $y = \pi^{(d-1)}(x)$ and $\pi(y)$ be $y$'s parent. If $L(\pi(y),d) \neq L(y,d-1)$ then $y$ must have a sibling $z$ with a leaf at depth $d$. We can associate the $d$ vertices on the path leading to the leaf (including $z$) to $\pi(y)$; note that vertices associated to different parents of $x$ are distinct.

For each element in $\\{L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\\}$ choose a representative $\pi^{(d)}(x)$ with the maximal $d$, and let $I$ be the set of all such $d$'s. In particular, if $\pi^{(d)}(x)$ is a representative then $L(\pi^{(d)}(x),d) \neq L(\pi^{(d-1)}(x),d)$, and so $\pi^{(d)}(x)$ has $d$ vertices associated to it. We deduce that $$ \sum\_{d \in I} d \leq n. $$ In particular, $I$ can contain at most $\sqrt{n}$ numbers larger than $\sqrt{n}$, and so $|I| = O(\sqrt{n})$.
> 3 votes

---
Tags: trees, upper-bound
---


# Question
Title: Query regarding the structure of Graph over All (known/unknown) NPC Problems?
Let us consider the set of all NPComplete problems. Since every problem in the set is Reducible to/from at least one known NPComplete problem, lets create a directed Graph with the following conventions:

1. If a problem B is Reducible from Problem A, create an edge from A to B. We assume an oracle who knows all possible reductions who creates the edges.

Here are a few questions regarding the Graph.

Q1. Is the graph strongly connected (i.e. every problem in the Graph is reachable from or reducible from every other problem for every instance?

Guess: I presume the answer is yes.

Q2. For any two problems (say A, B), no matter what the distance b/w them is, there is guaranteed at most Polynomial Blowup in problem size when we reduce, from A to B?

Guess: Unsure. For any problem P, if we reduce from one of its neighboring problem, there is polynomial increase or decrease in space. But, not sure if it holds if the problems are arbitrarily large distance apart. The definition of NPC, needs one single reduction in Polynomial time, but space analogue of reduction for All NPC Problem pairs seems out of reach.

# Answer
> 3 votes
1. The definition of **NP**-complete is that the problem is in **NP** and every problem in **NP** (including every other **NP**-complete problem) is reducible to that problem. So the graph you describe is not only strongly connected: it is a complete graph.
2. By the above, the distance between any two problems is 1. But, even if you follow a longer path of $k$ reductions, where the $i$th has polynomial blow-up $p\_i$, the total blow-up for an input of size $n$ is $p\_k(p\_{k-1}(\cdots p\_1(n)\cdots))$, which is still a polynomial.

---
Tags: complexity-theory
---


# Question
Title: Reducing k Vertex Cover to SAT (last clause problem)
I am working on a transformation from k Vertex Cover to SAT and I have some issues regarding the last clause in the boolean formula.

Here is my approach: $$\forall \text{ nodes } n\_i \in V, \text{ invent variables } v\_i$$ $$\forall \text{ edges } (n\_i, n\_j) \in E, \text{ invent the terms } (v\_i \lor v\_j) \Rightarrow C\_{edges}$$

Is this approach correct or am I missing something?

# Answer
First of all, the problem of vertex cover asks whether there is a vertex cover with *at most* $k$ vertices. Fortunately, there is a vertex cover with at most $k$ vertices iff there is one with exactly $k$ vertices, so your choice of looking for a vertex cover of size exactly $k$ is fine.

Second, you need to describe everything as a CNF, that is, a collection of clauses. You can't just include $$ y\_{i,j} \equiv (y\_{i-1,j} \land \lnot v\_i) \lor (y\_{i-1,j-1} \land v\_i). $$ Fortunately, every formula on $t$ variables can be written as a CNF having at most $2^t$ clauses (exercise), so you can turn this formula into a CNF of constant size.

Finally, you say that you "should write $y\_{nk}$ in terms of $v\_1 \cdots v\_k$", but there is no such requirement. An instance of SAT is just a bunch of clauses. You can use whatever variables and clauses you want; the distinction between original variables $v\_i$ and extension variables $y\_{i,j}$ is all in your head. If you want to force $y\_{n,k}$ to be true, you can just add a singleton clause $y\_{n,k}$.
> 4 votes

---
Tags: complexity-theory, reductions, satisfiability
---


# Question
Title: Formal way to model or describe distributed systems architecture
I've been tasked to create the systems architecture for a distributed system.

One approach to designing this system is to pick systems architecture patterns, and then evaluate different technologies that implement those architectural patterns.

For example, a particular architecture might call for a message bus, and given that, I could choose between various off-the-shelf open source or commercial projects that implement a message bus.

While this approach yields a nice white-board diagram, and a high-level understanding of how the system will work, some drawbacks are:

* its difficult to gauge the performance of the system as a whole without fully implementing it
* its difficult to determine how well each pattern / implementation will mesh with the other components
* because of that, choosing between patterns tends to be gut feelings similar to "Kafka is cool, I used it on project X and it did really well"
* there are no hard guarantees about the performance of the system as a whole (consistency, availability, etc)

Is there a formal approach to modeling distributed systems? Ideally one that provides a way to abstract patterns, and provide analytic tools for making predictions about the behavior of the system?

# Answer
I am not sure what you mean by "formal approach" but have you looked at Petri Nets? Many consider Petri Nets to be a "formal approach".

Personally, I use Petri's net elements (Place, Transition, Input, Output) to organize my computer program (logic annotations to net elements). I also use it to organize requirements (annotations meant for human interpretation). I find it useful to begin with a diagram (technically, graphical annotations to net elements but if each graphic represents one and only one net element then the diagram may be used to generate the net elements). Then to aid my memory I use forms to create the annotations. Based on the diagrams and the forms, I create my computer programs. For more information about this check out "Net Elements and Annotations for Computer Programming: Computations and Interactions in PDF".

Sometimes, I create a "high-level" diagram based on a Petri Net diagram to create a view of the system. \[A high-level (Petri Net) diagram is a Petri Net diagram where one or more than one graphic object represented more than one net element\]. Sometimes, I begin with a high-level diagram and break it down to a Petri Net diagram. In the "high-level" case, the form views are also applicable.
> 1 votes

---
Tags: distributed-systems
---


# Question
Title: How to calculate sum of binomial coefficients efficiently?
I want to compute the sum

$$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+\dots+\binom{n}{k} \bmod 10^9+7$$

where $n$ and $k$ can be up to $10^{14}$ and $k\le n$.

I found several links on stack overflow to calculate sum of binomial coefficients but none of them works on large constraints like $10^{14}$. I tried doing it by changing series using the relation $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ and came up with a brute force solution which is of no use. Is there any way to do it efficiently?

This question is from the TCS codevita 2016 round 2 contest, which has ended.

# Answer
Hint: Use Lucas's theorem.

In general, any time a programming contest problem wants you to compute something mod $p$, check for opportunities to reduce everything mod $p$ before doing any further work.

---

## Spoilers

Don't peek at any hint until you've spent a good amount of time thinking about the previous one!

A more in-depth hint if the previous wasn't enough:

> Let $p=10^9 + 7$. Use Lucas's theorem to express $\binom{n}{i}$ in terms of functions of $n \bmod p$ and $i \bmod p$. Simplify the resulting sum by grouping terms.

If that's *still* not enough of a hint:

> Consider the case where $k$ is a multiple of $p$. You should be able to come up with an efficient algorithm for that whose running time is something like $O(k/p)$.

Then for a final answer:

> Generalize to the case where $k=ap+b$. You should be able to express this as a sum of the previous form, plus $b$ more terms. As a result you should be able to achieve a final running time of $O(p)$.
> 12 votes

---
Tags: arithmetic, computer-algebra
---


# Question
Title: Are vector clocks useful in centralized systems?
Vectors clocks seem to be a common way to synchronize the partial ordering of events in a distributed, peer-to-peer, system across all clients.

Is there any benefit to using them in a centralized system, where one node in the system has the power to order all events anyway, to order events? If one computer can decide the order anyway, there would be no need for vector clocks, right?

# Answer
No, there's no need for a vector clock in a centralized system.

A vector clock uses a $N$-vector of timestamps, where $N$ is the number of computers in the distributed system and the $i$th component of the vector block is a timestamp chosen by the $i$th computer. In a centralized system you'd use a $N$-vector with $N=1$, so it just reduces to a single number instead of a vector. In other words, instead of a vector, all you need is a single timestamp, where the timestamp is chosen by the central computer.
> 6 votes

---
Tags: distributed-systems, clocks
---


# Question
Title: Algorithm for cycle-detecting comparison
I am looking for an algorithm that I can use to compare nested and potentially recursive data structures, for example to implement the Scheme `equal?` function. `equal?` recursively compares two objects for equality and properly handles cycles. Specifically, the algorithm needs to return true iff the (possibly infinite) unfoldings of the graphs would be equal, e.g.

```
(letrec ((a (cons 1 (cons 2 a)))
         (b (cons 1 (cons 2 (cons 1 (cons 2 b))))
  (equal? a b))

```

is true because `a` and `b` are both cyclic lists that repeat the sequence (1 2) infinitely.

Destructive modification of traversed nodes is thread-unsafe, requires a spare bit in object headers, and requires a separate traversal to reset the bit. Using a hash table to store object addresses is not safe in the presence of a moving garbage collector unless the GC is blocked for the duration of the traversal (so the operation cannot be implemented except as a primitive).

# Answer
There is no *pure* way to detect cycles, where by pure I mean without caring about representation details such as object addresses. If you only allow examining data by comparing fields at base types, then there is no way to distinguish e.g. a cyclic list from a very long list. If you start examining

```
(1 2 3 4 5 6 7 8 9 10 11 …
(1 2 3 4 5 6 7 8 9 10 11 …

```

then maybe one of them is the list `(1 2 3 4 5 6 7 8 9 10 11)` and the other is `(repeat (1 2 3 4 5 6 7 8 9 10 11)` where `(repeat cycle)` builds a cyclic list that repeats its arguments — but you need to examine one more node to find the difference. Since the difference could be arbitrary far, there's no way to prove that two cyclic lists are equal.

The most practical solution is to compare object addresses to detect cycles. I expect that this is how most Scheme implementations do it. This requires some knowledge of how the garbage collector works, and specifically the ability to temporarily prevent it from relocating any object that is within the already-traversed part of the data structure. Locking GC moves might not hurt much, it depends on the GC technology: a mark-and-sweep GC doesn't need to move objects.

By the way, mark-and-sweep GC usually detect cycles by using a spare bit in the object. But that doesn't generalize well to arbitrary processing of arbitrary data structures.

If you're building your own data structure, as opposed to having to cope with arbitrary data structures like `equal?`, then a good approach is to not store cycles. Purely functional data structures typically don't have cycles in the first place since they can only create cycles with a statically-known structure which is not very useful. As with many problems in computing, this is solved by adding a level of indirection: instead of having the data structure contain a pointer chain that loops back to itself, have it contain references, i.e. the data structure is represented as some kind of map from identifiers from elements and nested data structures are stored using their identifier. When doing this, it's useful to perform hash consing, i.e., when applying a constructor, verify if the result is already referenced in the map and if so use the existing identifier rather than making a new one. This can save memory, and also processing time since traversal algorithms never need to handle the same data structure twice. In particular, with this trick, you can test equality of data structures by simply testing equality of identifiers.
> 2 votes

---
Tags: algorithms, data-structures, graph-traversal
---


# Question
Title: A Turing Machine that exclusively accepts an infinite string
While reading some of proofs in Computability Theory, I came up with following conclusion:

We can design a Turing Machine which exclusively accepts finite strings (obvious).

Now while trying the same for infinite string, I came up with the following conclusion :

There exist no Turing Machine which exclusively accepts infinite strings.

Proof : Since acceptance in context to Turing Machine is defined in terms of finite amount of time, therefore every time we say that an infinite string $w$ is accepted by a Turing Machine, we usually talk about searching a "finite pattern" in $w$. So while designing a machine for $w$ there exist a $w'$ which is finite and contains the same "finite pattern" which we try to find in $w$.

Example of "finite pattern" : A string that contains a 0. (Assuming Binary Strings)

So my question is that is my proof right? and if yes, is there a better way to prove this?

# Answer
In contrast to the commenters, it is perfectly possible to define a Turing machine formalism whose input can be infinite. Let $\Sigma$ be an alphabet, and let $\\#$ be a symbol not in $\Sigma$. We say that a Turing machine $T$ accepts a finite word $w \in \Sigma^\*$ if it halts in an accepting state when the tape is initialized by $w \\#^\omega$ (i.e., $w$ followed by infinitely many copies of $\\#$; I assume for simplicity that the tape is only one-way infinite). Similarly, $T$ accepts an infinite word $w \in \Sigma^\omega$ if it halts in an accepting state when the tape is initialized by $w$.

We say that a language $L \subseteq \Sigma^\* \cup \Sigma^\omega$ is *$\omega$-computable* (non-standard terminology) if there exists a Turing machine which halts on all inputs, and accepts exactly the strings in $L$. We say that $L$ is *$\omega$-r.e.* if there exists a Turing machine that accepts the strings in $L$, and never halts on strings not in $L$.

Under this definition, the language $\Sigma^\*$ consisting of all finite words is not $\omega$-computable (as we show below), but is $\omega$-r.e. (exercise). It then follows that $\Sigma^\omega$ is not $\omega$-r.e., and in particular not $\omega$-computable (though we can show the latter directly).

Suppose that $T$ is a machine which halts on all inputs and accepts $\Sigma^\*$. In particular, it halts on $\sigma^\omega$, where $\sigma \in \Sigma$ is arbitrary. Suppose that it halts after $N$ steps, at the rejecting state $s$. Then $T$ also halts on $\sigma^N$ (exercise), at the same state $s$, thus rejecting the finite word $\sigma^N$.

The same proof also shows directly that no Turing machine accepts $\sigma^\omega$.
> 4 votes

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


title: Finite automaton - language acceptance

text:
# Question
Title: Finite automaton - language acceptance
In the book "The New Turing Omnibus", an excercise reads as the follows:

> "Show that no finite automaton can accept the language consisting of all words of the form $a^n b^n, n=1,2,3,...$ The formula represents $n$ a's followed by $n$ b's."

I have no idea why a finite automaton shouldn't accept such words. Couldn't one simply design an automaton that reads a word and always outputs "Accepted"?

# Answer
Check the definitions. The language accepted by an automaton is the set of strings it accepts. So, for an automaton to accept a particular language (e.g., $\\{a^nb^n\mid n\geq 1\\}$), it must not only accept every string in the language, but also reject every string not in the language. Your suggestion of the automaton that just accepts every input meets the first criterion but not the second.
> 9 votes

# Answer
In formal language theory, when we say an automaton accepts a language, we mean that it accepts exactly that language, no more, no less.

Your automaton accepts words in $a^n b^n$, but also words with different numbers of as and bs. No finite automaton is capable of distinguishing words with equal numbers of as and bs, and words with different numbers.

You will want to read up on the pumping lemma in order to prove this.
> 4 votes

# Answer
Let $\cal A$ be a deterministic finite automaton that accepts the language $L = \\{a^n b^n : n \geq 0\\}$. Denote by $q\_n$ the state that $\cal A$ arrives at after reading the word $a^n$. Since $\cal A$ has only finitely many states, by the pigeonhole principle we must have $q\_n = q\_m$ for some $n \neq m$.

What happens when $\cal A$ reads $b^n$, starting at $q\_n$? On the one hand, since $a^n b^n \in L$, $\cal A$ must arrive at an accepting state. On the other hand, since $a^m b^n \notin L$ and $q\_m = q\_n$, $\cal A$ must arrive at a rejecting state. This contradiction shows that $\cal A$ cannot exist.

This argument can be generalized to give a neat algebraic characterization of the regular languages, known as *Myhill–Nerode theory*. Given a language $L$, say that two words $x,y$ are equivalent if for all words $z$, either $xz,yz \in L$ or $xz,yz \notin L$. If $x,y$ are *not* equivalent that any automaton accepting $L$ must reach different states after reading $x$ and $y$. Hence if there are infinitely many pairwise inequivalent words, $L$ is not regular. The Myhill–Nerode theorem states that the converse also holds: if any collection of pairwise inequivalent words is finite, then $L$ is regular.

Normally this is stated in terms of *equivalence classes*: $L$ is regular if and only if the Myhill–Nerode relation (the equivalence relation defined in the preceding paragraph) has finitely many equivalence classes. Moreover, if $L$ is regular and the Myhill–Nerode relation has $n$ equivalence classes, then every DFA accepting $L$ must have at least $n$ states, and there is a unique DFA with exactly $n$ states, known as the *minimal DFA*.
> 3 votes

# Answer
A finite automaton does not has a memory unit associated with it. It only knows its current state and behaves according to the input provided to the current state.It cannot remember how many 'a's it has already read and how many 'b's it has to further count so as to make number of 'a's equal to number of 'b's ( as 'n' is a variable entity). But if we provide specific number of 'a's and 'b's ( like a3b3 or a5b5) then the automaton will have a dedicated state for every alphabet read.

# Another ways of getting it

A finite automaton is a machine to accept regular languages. We can prove by pumping lemma that anbn is not a regular language.
> 2 votes

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


# Question
Title: Why do Tarjan's and Kosaraju's algorithms for finding strongly connected components have the same running-time complexity?
I followed an explanation of Kosaraju's and Tarjan's strongly-connected components algorithms, and they say that both have O(|V|+|E|) time complexity.

That didn't make sense to me since Kosaraju uses two DFS passes and computes the transposed graph, but Tarjan's use only one DFS.

# Answer
> 3 votes
> > they say that both have O(|V|+|E|) time complexity.
>
> that didn't make sens for me since Kosaraju use two dfs pass and compute transpose graph, but Tarjan's use only one dfs

If you check the definition of Landau notation you will see that it does not say which function is smaller, that is (here) which algorithm is *faster*. It ignores constant factors.

Both algorithms have running times in $\Theta(|V| + |E|)$; that does not preclude one of them being $2^{100}$ times faster than the other for all $n \leq 2^{100}$.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: The importance of the language semantics for code generation and frameworks for code generation in model-driven development
I am implementing worflow where the code in industrial programming languages (JavaScript and Java) should be generated from the formal (formally verified) expressions (from ontologies as objects and rule formulas as behaviors). What is the best pratice for such code generation? Are some frameworks available for this?

In my opinion the semantics of the programming language is required. And I should be able to do the code generation in two steps: 1) translate my formal epxressions into semantic expressions of the target language; 2) translate semantic expressions into executable code. In reality I can not find any work that connects semantics of programming language with the code generation.

Is there special kind of semantics of programming languages that is usable not only for the analysis of the programs but also for the generation of the programs?

My guess is that it should be really useful approach for generating formally verified code but I can not find research work about this. Are there trends of better keywords avilable for this?

*Maybe - more relevant question is - what kind of compilers/translators the Model Driven Development tools use for the generation of source code (platform dependent code) and how semantics of programming language can be used for the construction of such compilers?*

*Note added. There already is complete unifying (denotational and operational) semantics of Java, JavaScript and other industrial programmin languages in the K framework. So - this is more question about application of K framework for code generation is that is possible at all?*

# Answer
> 4 votes
In general when we talk about code generation (or model-to-model transformation in general), clearly defined semantics is quite important, since such transformations usually make sense when both the source and the target model *semantically match* according to some criteria. For example, programmers might describe the behaviour of a program with a formal specification, which, according to the semantics, defines possible implementations in the target language (i.e. outputs of code generation). Failing to precisely define the semantics might lead to *ambiguous or, in general invalid, transformations*.

> Is there special kind of semantics of programming languages that is usable not only for the analysis of the programs but also for the generation of the programs?

In general, there is no need for a special kind of semantics for targeting generation of programs. However, different code generation systems target different domains of code generation and thus leverage different kinds of programming languages and their semantics. (Some overview of code generation in the context of program synthesis can be found in \[1\]).

There exists a body of work for which a programming language is coupled with language verification and program synthesis (described below). A seemingly well-fitting example of this is the Leon framework, which uses a subset of Scala as the main programming language, that expresses both programs and formal specifications. The framework allows not only verifying that the program matches the given specification (again, strictly defined by the semantics of the language and the interpretation of the logic used in the specification), but also generating code. In the latter case, programmers can only give formal specifications of the program in terms of its precondition and postcondition and the framework, it's code generation part (i.e. its synthesizer), generates the program that matches the given specification \[2\].

> My guess is that it should be really useful approach for generating formally verified code but I can not find research work about this. Are there trends of better keywords avilable for this?

One of the fields that seems to be closely matching what you described is software synthesis. Program synthesis is the task of automatically discovering an executable piece of code given user intent expressed using various forms of constraints such as input-output examples, demonstrations, natural language, etc \[1\].

> In reality I can not find any work that connects semantics of programming language with the code generation.

In general, the compiler for many general-purpose modern (high-level) languages perform some form of code generation that has to satisfy the rules of the language semantics (i.e. its language specification). E.g. the compiler for the Scala programming language emits Java bytecode---which can be thought of as a language which elements semantically closer match the instructions of the actual hardware---according to the Scala language specification.

> \[About compiler and other tools for\] Model Driven Development useful for code generation. What is the best pratice or framework for code generation?

Although, in my answer, I was focusing on the connection of the semantics of the programming language and code generation in the context of (general-purpose) program synthesis, these concepts are by all means applicable to other domains or practices such as Model-Driven Development. For general pointers on this direction, it might be useful to check out books that try to summarize them \[4\], \[5\].

> So - this is more question about application of K framework for code generation is that is possible at all?

Although, it might be the most suitable for your problem and intended use, there are other alternatives that might also work and perhaps could work for you as well, such as some of the transformation languages like Stratego or rewriting systems like Maude.

\[1\] Gulwani, Sumit. "Dimensions in program synthesis." In Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming, pp. 13-24. ACM, 2010.

\[2\] Kneuss, Etienne, Ivan Kuraj, Viktor Kuncak, and Philippe Suter. "Synthesis modulo recursive functions." Acm Sigplan Notices 48, no. 10 (2013): 407-426.

\[3\] Scala Language Specification

\[4\] Brambilla, Marco, Jordi Cabot, and Manuel Wimmer. "Model-driven software engineering in practice." Synthesis Lectures on Software Engineering 1, no. 1 (2012): 1-182.

\[5\] Milicev, Dragan. Model-driven development with executable UML. John Wiley & Sons, 2009.

---
Tags: programming-languages, semantics, model-checking, code-generation
---


title: Back propagation in neural networks

text:
# Question
Title: Back propagation in neural networks
I just finished watching these 3 Coursera videos on back propagation in neural networks. I get the idea of what we're trying to do, but I don't get how we achieve that by calculating error in each step as `weight * cascaded error` (eg. the formula at the top right of screen at 12:07 in the linked video). Let's say we start off with all the weights (theta) at zero. Wouldn't back propagation always calculate 0 error for everything, causing nothing to change?

# Answer
> 1 votes
**Weights must be initialized to random, distinct, small values.**

If all the weights are initialized to zero, our optimization function (eg. gradient descent) will not work. According to a later video, it's a problem of symmetry that will happen when you initialize weights to the same value. So if you used 0.4 instead of zero, the same problem would happen.

From course material:

> When training neural networks, it is important to randomly initialize the parameters for symmetry breaking. One effective strategy for random initialization is to randomly select values for weights uniformly in the range \[-x, x\]. One effective strategy for choosing x is to base it on the number of units in the network. A good choice of x is `x = sqrt(6) / sqrt(in + out)` where `in` and `out` are the number of units in the layers adjacent to \[the weights\]. This range of values ensures that the parameters are kept small and makes the learning more efficient.

---
Tags: machine-learning, neural-networks
---


title: Relationship between PP and PH

text:
# Question
Title: Relationship between PP and PH
Toda's theorem says that $PH \subset P^{PP}$. Does this imply any relationship between $PH$ and $PP$ that does not involve oracles? Does it imply either that $PH \subset PP$ or that $PP \subset PH$? Is it known or conjectured whether either of those hold?

# Answer
> 3 votes
No, it's not known whether $PH \subset PP$, and it's not known whether $PP \subset PH$. Neither of those is implied by Toda'a theorem.

This blog article cites a paper by Beigel giving some weak evidence to suspect that $PH \not\subset PP$ (that $PH$ is not contained in $PP$). Please be warned that this is very weak evidence and doesn't really prove anything. The result says that there's a relativized world where $P^{NP}$ is not contained in $PP$. It follows that there's a relativized world where $PH$ is not contained in $PP$. This might suggest the conjecture that $PH \not\subset PP$. Or, at least, it suggests that proving $PH \subset PP$ might require special proof techniques (non-relativizing proof techniques; and most, but not all, known proof techniques do relativize).

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


# Question
Title: Finding a value in a sorted array in log R time, R is the number of distinct elements
The standard binary search algorithm gives log N time, where N is the total number of elements in the array. When the array has duplicates, I don't see how you could detect those duplicates ahead of time. (Iterating through the array takes N time, which is too much.) Consequently how do you improve the performance from log N to log R?

# Answer
> 6 votes
There is no such algorithm. Here's an information-theoretic proof that it can't be done, inspired by gnasher79's answer.

Let's focus on the special case where $R=3$. Suppose there is a constant $c$ and an algorithm that examines at most $c$ elements of the array, regardless of $n$. Then this algorithm can't possibly solve your problem.

In particular, consider all arrays of the form $\[0,\dots,0,1,2,\dots,2\]$, i.e., containing some number of 0's, followed by a single 1, followed by 2's. Let's imagine what the algorithm does when you ask it to find a $1$. There are $n-1$ different possible positions for the $1$. However, after doing $c$ probes, the algorithm learns only $c \lg 3$ bits of information about the position of the $1$. Thus, if $n-1 \> 2^{c \lg 3}$, the algorithm can't possibly work correctly for all such arrays: there exists some pair of arrays where the algorithm outputs the same thing in both cases, but the correct answers differs, so the algorithm must be wrong for at least one of those two cases. In other words, if we take $n$ to be sufficiently large (namely, $n\> 3^c + 1$), the algorithm will be incorrect.

This implies there is no algorithm for the case $R=3$ whose running time is upper-bounded by a constant.

It follows that there is no algorithm whose running time is $O(\lg R)$ (and whose running time doesn't depend on $n$): if there was, plugging in $R=3$ would give us a $O(1)$-time algorithm for the special case where $R=3$... but I just proved that no such algorithm can exist.

---

However, the special case $R=2$ can be solved in $O(1)$ time: simply look at the first and last element of the array, and pick whichever one matches the value you're looking for.

# Answer
> 3 votes
It can't be done.

Assume you are looking for an element x, and it is guaranteed that x is an array element. Assume there are n array elements. You read array elements until you know one that equals x. I change array elements to create the worst case for you. Assume R ≥ 3 and x occurs exactly once.

If n ≥ 2 then you don't know which one equals x. If n ≥ 4 then whatever element you examine, there are at least two elements either to the left or to the right of it, so you may be left with a range of ≥ 2 elements containing x, so you can't solve the problem examining only 1 element. If n ≥ 8 then whatever element you examine, there are at least 4 elements either left or right of it, so you can't solve it in two steps, and so on.

If $n ≥ 2^k$ then you need to examine at least k array elements in the worst case, for any R ≥ 3. Since k is unlimited, finding an array element in guaranteed O (log n) is **impossible**.

So there's a little bit missing: There is no upper limit on the number of steps needed if R = 3. However, O (log R) means: Less than c * log R for some c *for all large R*, the case R = 3 doesn't mean anything.

But it's simple: Take an arbitrary R ≥ 3. Take an array of R-3 numbers from 1 to R-3, an arbitrary number of items equal to R-2, one item R-1, an arbitrary number of items equal to R. And you look for the item R-1. Even in this special case, even if I *tell* you the structure of the array, you still have to solve a problem equivalent to the case R = 3, which cannot be done with any limit to the number of steps, and which therefore cannot be done in c log R steps.

# Answer
> 3 votes
If each item repeats $N/R$ times, this result is automatic, since binary search will take $\log( N/R)$ fewer steps to find a value. Specifically, if a searched value repeats C times, the lower and upper brackets cannot get closer than C without locating the match, so $log C$ iterations are avoided, even if the searcher doesn't know C (no a priori knowledge is needed).

$\log N - \log(N/R) = \log R$

In the more general case where each item $i$ occurs $c\_i$ times, if the items are searched in proportion to their frequency in the array, the average cost is

$\sum \limits\_{i=1}^{R}{{c\_i \over N}(\log N -\log c\_i )} = \sum{-{c\_i \over N}\log {c\_i \over N}} = \sum -p\_i \log p\_i$

which is the entropy of the multiset. (There's an extra $1$ in there which I dropped for complexity-class purposes, eg entropy 0 still takes one probe.)

# Answer
> 3 votes
> how do you improve the performance from log N to log R?

As you can see from answers above **this is impossible to do**. But its possible with little bit of *cheating*.

Assumptions:

1. The array doesn't change.
2. Queries for each element are equally likely.

Whenever you get query for some element $x$. Compute the location of $x$ and the range of indices where it occurs. It can be done in $O(\log n)$ time using binary search (e.g., lower\_bound and upper\_bound in C++). Keep $x$ and the range of locations where it appears in the main array. Maintain a balanced binary tree with all of the elements seen so far and their range of locations (one leaf node per element).

After $O(R\log R)$ queries (expected value using assumption 2) you will have seen every element at least once. Now you know the range of locations of all elements of the array. Now you can find any new element in $O(\log R)$ time by lookup in the binary tree.

Of course you don't have to wait until you've seen all the elements to start using the binary tree. Any time you want to find a value $x$, you can first look it up in the binary tree; if it's not there, you can look it up in the main array and then add it to the binary tree. But once you've made about $O(R \log R)$ queries, you should expect each future query to take $O(\log R)$ time.

If you plan to make at least $\Omega(R \log N)$ queries, the amortized running time will be $O(\log R)$ time per query.

This could be useful in the real world if $R \ll n$.

---
Tags: algorithms, search-algorithms, binary-search
---


# Question
Title: Auction where each bidder bids on a bundle of items
Is there some optimal solution in an auction where each bidder bids on a bundle of items?

# Answer
> 4 votes
This problem is NP-hard, by reduction from 3-dimensional matching.

An instance of 3-dimensional matching involves three disjoint vertex sets $X,Y,Z$ and a set $T \subseteq X \times Y \times Z$ of triples of the form $(x\_i,y\_j,z\_k)$. The goal is to find a subset $T\_0 \subseteq T$ such that each vertex of $X \cup Y \cup Z$ appears in at most one triple of $T\_0$, and the cardinality of $T\_0$ is maximized.

Given an instance of 3-dimensional matching, we can construct an auction with bidders $X$ and items $Y \cup Z$. For each $(x,y,z) \in T$, we'll have $x$ bid \\$1 on the pair of items $y,z$. Now the optimal set of accepted bids for the auction is exactly the maximum 3-dimensional matching, so any algorithm to solve your problem would also solve 3-dimensional matching.

Since 3-dimensional matching is known to be NP-hard, it follows that your problem is also NP-hard, and in particular, there isn't likely to be any efficient algorithm for your problem.

The same reduction also shows that your problem is APX-hard, i.e., there is some $c\>1$ such that there does not exist any $c$-approximation algorithm for your problem (unless P=NP).

I don't know whether there might be an approximation algorithm for some constant approximation factor. It's known that 3-dimensional matching can be approximated in polynomial time with a $3/2 + \varepsilon$ approximation factor; you might check whether any of those algorithms can be adapted to provide suitable solutions for your problem. For instance, one very simple approach might be to find a maximal matching of the associated hypergraph; this will give a $1+k$ approximation, if every bid mentions at most $k$ items. I don't know if you can find maximal matchings in hypergraphs in polynomial time, like you can in ordinary graphs.

---

## Practical algorithms

If you have to deal with this problem in practice, I suggest formulating it as an integer linear programming (ILP) problem and then applying an off-the-shelf ILP solver.

Introduce zero-or-one variables $x\_i$, with the intended meaning that $x\_i=1$ means that the $i$th bid is accepted. Each constraint "at most one bid is accepted from each person" turns into a inequality of the form $\sum\_{i \in S} x\_i \le 1$. Each constraint "each item appears in at most one accepted bid" turns into another inequality of the same form. The objective function is a linear function of the $x\_i$'s. Now apply an off-the-shelf ILP solver, like CPLEX.

# Answer
> 0 votes
Problem definition: There are k ≥ 1 bids. Each bid $B\_i$ consists of a price $p\_i$ and a set $X\_i$ of integers. A subset S of the integers 1 to k is acceptable if $X\_i$ and $X\_j$ have no element in common if i ≠ j and i, j are elements of S. Find an acceptable set S that maximises the sum of $p\_i$ for i element of S.

Remember all bids with $p\_i$ ≤ 0. Then remember all bids where $X\_i$ is the empty set, remove them, and later add them back to the optimal solution (someone is offering money for nothing; we take that).

Then remove any bid $B\_i$ if there is a bid $B\_j$, j ≠ i, where $p\_i ≤ p\_j$ and $X\_i$ is a superset of $X\_j$, until no further bids can be removed. Sort the remaining bids on $p\_i$ divided by the number of elements of $X\_i$ in descending order, so the most promising bids come first.

And now you do an exhaustive search: You either accept the bid with the highest ratio price / number of items or not (you have the choice). You then accept the bid with the second highest ratio or not - you may not be able to accept the bid if you earlier accepted a bid including any of its items. And so on. You record the highest price found so far. And you stop examining futher bids if you can prove that you are not going to beat the highest price.

Before starting the search, you would also try if you can extract independent groups: Create a set, starting with one bid $B\_i$, then adding bids $B\_j$ where $X\_i$ and $X\_j$ have elements in common until no more bids can be added. These bids can then be handled separately from all the other bids.

In your example: Bid 4 is eliminated because it's inferior to bid 1 and bid 2. The sets (Bid 1, 2) and (Bid 3) are independent of each other.

---
Tags: algorithms, optimization, bipartite-matching
---


# Question
Title: How to Determine Existence of Turing Reducible Languages?
Are *finite* and *recursive* instances of $L$ possible with the following constraints?

$\text{L $\subseteq$ {0,1}\*}$ and $L \leq HALT \leq \overline L$ where $\overline L = \\{\text{ x $\in$ {0,1}\* : x $\notin$ L }\\}$.

**NOTE:** Raphael and Yuval kindly pointed out that I was overlooking $\overline L$ is undecidable. Aside from this oversight, are there any *other* issues, e.g. conceptual misunderstandings, logical fallacies, etc. in the explanation below?

As I understand it:

1. A finite instance of $L$ is possible. Since the language is finite, an evaluating Turing Machine (TM) could not loop indefinitely on input, and consequently would halt either in an "accept" or "reject" state. Since the language stops on all inputs, it is recursive and thus can be reduced to $HALT$, which is recursively enumerable.
2. Since a finite instance (which is recursive) is possible, logically a recursive $L$ must also be possible.

# Answer
> 2 votes
To narrow down the search space, consider what you know about closure properties and HPL.

1. The class of decidable languages $R$ is closed against complement.
2. HPL is not in $R$.

You can conclude that $L \not\in R$;¹ otherwise, $\overline{L} \in R$ and therefore $\mathrm{HPL} \not\leq\_T \overline{L}$.

On the other end, you need that $L \in RE$ (the set of semi-decidable languages) -- otherwise $L \not\leq\_T \mathrm{HPL}$.

In combination, you need $L \in RE \setminus R$ which answers your question².

---

1. In particular, $L$ can not be finite since all such languages are decidable. The decider just checks a hard-coded table of all words in the language. With the same table you can also decide the complement.
2. Note how this implies $\overline{L} \not\in R$ which is enough for $HPL \leq\_T \overline{L}$.

# Answer
> 0 votes
You haven't specified your notion of reduction, so I'm assuming a computable oracle reduction. Any language reducible to a computable language is computable. HPL (usually known as HALT) is not computable. Hence HPL cannot be reduced to $\overline{L}$ for any computable $L$.

---
Tags: computability, reductions
---


# Question
Title: Find a string that covers many sets of binary strings with don't-cares
Consider $N$ sets $S\_1,S\_2,....,S\_{N}$ of binary strings with don't-cares ($X$) with $|S\_i| = n$ and the length of all strings is $m$.
In my application, $N=1000$, $n=100$ and $m=500$.

I have to find atleast one binary string with all set bits (either $1$ or $0$) that is compatible with at least one string of each set. Two strings are compatible if they are bit-wise similar. As we know $X$ bits are similar to both $0$ or $1$. For example, consider string $A=10XX0$ and string $B=X011X$. Here string $A$ and $B$ are compatible with each other.

As we can see, due to the size of each string ($m=500$), it's impossible to find a solution with brute force (i.e. create all possible strings of length $m$ and compare each with all strings of all sets). So, I am looking for a reasonable heuristic to find the solution.

# Answer
> 3 votes
Your problem is NP-hard. It's basically a variant of SAT. You shouldn't expect any algorithm that is provably efficient. Instead, I recommend you use an off-the-shelf SAT solver; since your problem is basically SAT, that's probably about as good as you can do, without a lot of effort tuning for your particular scenario.

**NP-hardness:** In particular, if every element of every set $S\_i$ has exactly $m-1$ don't-cares (has only a single bit set to 0 or 1), then your problem becomes exactly $n$-CNF-SAT with $m$ variables and $N$ clauses. We know that $n$-CNF-SAT is NP-hard; it follows that this special case of your problem is NP-hard, and thus your problem in general is NP-hard.

**Using a SAT solver:** Introduce variables $x\_1,\dots,x\_m$ representing the string you're trying to find. Then we obtain a formula of the form

$$\Psi(x\_1,\dots,x\_m) = \bigwedge\_{i=1}^N \bigvee\_{j=1}^n \phi\_{i,j}(x\_1,\dots,x\_m),$$

where each $\phi\_{i,j}$ is a conjunction of literals. The goal is to find an assignment $x\_1,\dots,x\_m$ that makes $\Psi(x\_1,\dots,x\_m)$ true.

You can formulate this as a SAT instance by applying the Tseitin transform. In other words, introduce variables $y\_{i,j}$, then add CNF clauses enforcing that $y\_{i,j} = \phi\_{i,j}(x\_1,\dots,x\_m)$ as well as CNF clauses $(y\_{i,1} \lor \dots \lor y\_{i,n})$ for all $i$. The Tseitin transform tells you how to add the former clauses. In particular, you add the clause $(\neg y\_{i,j} \lor \neg x\_k)$ if the $j$th element of $S\_i$ has a 0 in its $k$th bit; add the clause $(\neg y\_{i,j} \lor x\_l)$ if the $j$th element of $S\_i$ has a 1 in its $l$th bit; and add the clause $(y\_{ij} \lor x\_k \lor \neg x\_l \lor \dots)$ if the $j$th element of $S\_i$ has a 0 in its $k$ bit and a 1 in its $l$th bit and so on. Or, use a SAT front-end that will let you input arbitrary formulas and will do the Tseitin transform for you -- for instance, STP is a nice tool for that purpose.

Then, let the off-the-shelf SAT solver look for a satisfying assignment for you.

# Answer
> 2 votes
Let $S = \bigcup\_{i=1}^N S\_i$ the set of all strings.

Here is a sketch of an algorithm. The idea is to start with a trie of all strings and eliminate one $X$ after the other, copying the membership information from $X$-subtries to its siblings.

1. Create a (ternary) trie of all strings in $S$; label each leaf for $w \in S$ with all indices $i$ for which $w \in S\_i$, for instance with a bit vector $\chi\_w$ (each).
2. For each node $v$ reached via an $X$-edge do:

1. For each leaf $w$ under $v$ and matching leaves $w'$ under the $0$- and $1$-sibling of $v$, set

    $\qquad \chi\_{w'} = \chi\_{w} \lor \chi\_{w'}$.

    If matching $w'$ do not exist, create them.
    2. Remove $v$.
3. Any leaf $w$ with $\chi\_w = (1, \dots, 1)$ is a solution.

Since step 2.1 may *double* the number of nodes in the subtree rooted in the parent of $v$ we do not get a polynomial bound on the running time. In fact, we will eventually create the binary trie of all strings that are compatible to *any* string in $S$ -- who may be legion.

Here are some ideas on how to speed up the algorithm, sometimes.

* Keep track of which leaves correspond to binary strings. As soon as you get one labelled with the one-vector, terminate.
* In step 2, prefer nodes on paths with as few $X$ as possible. (You can label leaves with this information during step 1.)
* In step 2, prefer nodes that cover more $S\_i$. (You can label nodes with this information during step 1, just like leaves.)

---
Tags: algorithms, strings, heuristics, enumeration
---