# Question
Title: Show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem on $n$ points?
The question is to show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem (ETSP) on $n$ points.

My attempt was using induction. So I start by:

* If $n=3$, then we have a triangle and there is only one tour.
* Assume that there are $(n-1)!/2$ distinct tours for a ETSP on $n$ points. Prove that there are $n!/2$ distinct tours for a ETSP on $n+1$ points?

+ Here I proceed like this:

    - for each tour $t$ from the $(n-1)!/2$ distinct tours do: add one point $n+1$.
        - for each edge $e=\\{v\_i, v\_j\\}$ in $t$ do: remove $e$ and create two edges $e\_1=\\{n+1,v\_i\\}$ and $e\_2=\\{n+1, v\_j\\}$. We have a new tour and in total we can create $n$ distinct tours.

        Since there are $(n-1)!/2$ distinct tours, we will have $n(n-1)!/2=n!/2$ distinct tours.

This gives the desired result but somehow long and complicated.

# Answer
We may reason in a combinatorial way.

There are $n!$ permutations of $n$ nodes, but that overcounts the number of tours in two different ways. Since tours are closed, we may start indifferently on any of the $n$ nodes, and we may choose the direction in $2$ ways. Therefore, each tour was counted a total of $2n$ times.

This yields the desired result.
> 7 votes

---
Tags: traveling-salesman
---


# Question
Title: Matching algorithm, match pairs: what would be the right way to do it?
How would you solve the following problem... Theres a table filled with data like this:

```
Data1: 50 51 48 55 50
Data2: 51 49 52 50 51
Data3: 49 53 50 51 48
Data4: 48 50 52 51 53
Data5: 47 50 51 54 49
Data6: 50 48 50 49 52
Data7: 51 50 51 49 51
Data8: 48 51 49 50 50
...

```

The goal is to create pairs from the table, based on similarity of the rows.

**As i learned from the comments, it is matching, thx :)**

A difference bigger than 3 is not allowed.

When values are close to each other, they should be paired, for example

```
Data2: 51 49 52 50 51
Data7: 51 50 51 49 51

```

have very close values and should be a paired/grouped. So if this is our first pair, what is the next one? And how to handle outliers (in the columns)? For example

```
Data1: 50 51 48 55 50

```

has in the fourth column the value 55. With the criteria no bigger difference than 3, the only possible companion is Data5:

```
Data5: 47 50 51 54 49
Data1: 50 51 48 55 50

```

But in cloumn 1 and 3 the delta is 3, so in the mean maybe it isnt such a good choice.

Outlier who couldnt be assigned because of the too big deviation, will not be considered. The algorithm has not to be efficient.

Maybe you can see that it is just not clear for me, how to check the data against each other. To match the best fitting rows together.

So to answer the question about the use: each datarow is one measured device. You need two devices for the signal reproduction. For the best reproduction result you need maximum coherence between those two. So perfect would be an ideal match. So the goal is to find the best matching devices in the table.

# Answer
> 2 votes
This isn't sorting: it's matching. The vertices of your graph are the data rows and there's an edge between two vertices if the two rows are compatible for pairing (e.g., have no difference bigger than 3, or whatever criterion you want to use). You're looking for a maximum matching, i.e., a biggest-possible pairing between compatible rows.

It's unclear in your question but you might instead want to define a weighted graph where the weight of an edge is the amount of compatibility (e.g., rows that are very close have a high weight, rows that aren't so close have a low weight, rows that are incompatible have no edge, as before) and compute a maximum-weight matching.

---
Tags: algorithms, sorting
---


# Question
Title: Minimum bits needed when representing a value in a set
I'm reading a paper entitled "Succincter" which discusses a compression scheme that involves encoding a value as a sequence of $M$ bits, along with a "spillover" value which can be recursively encoded.

The details of the encoding scheme are not really relevant for the purpose of this question. Rather, I am specifically interested in asking for some clarification regarding this following excerpt from the paper:

> Assume we want to represent a value from a set $X$ . Any representation in a sequence of memory bits will use at least $\lceil \log\_2|X| \rceil$ bits in the worst case, so it will have a redundancy of almost one bit if $|X|$ is not close to a power of two.

Okay, so I get the meaning here - the author is saying that if we want to represent any arbitrary element $e \in X$, then in the worst case we need at least $\lceil \log\_2|X|\rceil$ bits. But why is it $\log\_2|X|$ and not $\log\_2 \max X$?

For example, if I have a set $X = \\{1, 2, 1e10 \\}$, which contains 3 elements, I need at least $\lceil \log\_2 1e10\rceil$ bits in the worst case, not $\lceil \log\_2 3\rceil$ bits.

Or am I somehow misinterpreting the statement? The only thing I can assume here is that the author is implicitly assuming some kind of mapping table over an alphabet $\Sigma$ which we use to map each element in the set to an increasing value starting at 0. But this is never explicitly stated, and would seem to be a large assumption.

So am I missing something here?

# Answer
You can encode the set $X$ using only two bits: use $00$ to encode $1$, $01$ to encode $2$, and $10$ to encode $1e10$.

More generally, the exact identity of the elements of $X$ are not important. You can encode letters of the alphabet or even words, if you want.

You haven't defined what an encoding scheme is, so let me assume that it is a uniquely decodable code. Any uniquely decodable code for $X$ must contain a codeword whose length is at least $\log\_2 |X|$ (and so at least $\lceil \log\_2 |X| \rceil$). This follows from McMillan's inequality.
> 5 votes

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


title: Maximum weight sum in a subgraph

text:
# Question
Title: Maximum weight sum in a subgraph
Let $G = (V, E, W)$ be a weighted graph with positive and negative weights. I would like to find the set of vertices $V^\prime$ such that the sum of the weights of **the edges that they share** is the maximum you can get from $G$. I suspect that this is an NP-complete problem, so my question is whether this can be reduced to a known NP-complete problem. Since $V^\prime$ does not necessarily have to be the minimum subset that satisfies the constraint, I think I can't use the solutions for the vertex/set cover problems, so any ideas would be welcome.

# Answer
An easier problem to use would be max clique. We do the transformation as follows. We take the graph that we wish to find the max clique in and give all edges in it weight 1, and for all non edges we give weight (-)infinity (or if you dont like infinity an arbitrarily large number based on the number of edges total, negative enough so that if one is picked the total will always be negative). This problems solution will give us a clique since the negative infinity weight will prevent selecting anything that does not have edges between them for the solution. This clique is also the largest, as a larger clique would have a larger edge sum and we assume this algorithm returned the largest edge sum. This is therefor at least as hard as solving max clique, which is NP complete.
> 2 votes

---
Tags: algorithms, graphs, optimization, np-complete, reductions
---


# Question
Title: Chord algorithm - how to map nodes to keys?
I'm trying to understand Chord algorithm (for Peer-to-Peer systems) but I can't understand how it maps the documents to the nodes.

I have one example where we have:

* keys with 4 bits
* 5 active nodes with the following identifiers: 1, 5, 7, 10, 13

After mapping the documents to the nodes, we have:

Key 0 - Node 1

Key 2 - Node 5

Key 8 - Node 10

Key 11 - Node 13

Key 15 - Node 1

If somebody could help me with the steps that lead to this results I'd be truly grateful.

# Answer
> 1 votes
Chord implementations use a defined function which is used to map the key identifiers (0, 2, 8, 11, 15 in your case) to the node identifiers (1, 5, 7, 10, 13). In the example you provided, the function works like this:

```
NodeID = KeyID % N

```

where **NodeID** is the (identifier) node where the key will be inserted, **KeyID** is the identifier of the key to be inserted, and **N** is the total number of nodes.

After you calculate the **NodeID**, it might be the case that this **NodeID** does not exist. For example, when **KeyID** is 0, the **NodeID** will be 0. Since **NodeID** doesn't exist, it will be allocated to the next highest (existing) node identifier which is **NodeID** = 1.

The keys identifier can be calculated using some hash algorithm.

---
Tags: algorithms, distributed-systems
---


title: Regular Expressions to Automaton

text:
# Question
Title: Regular Expressions to Automaton
Is there any systematic (algorithmic) method to convert a regular expression like

$(a^\*)(b)(b^\*)(a^\*)c$

to an automaton (let's say a Buchi automaton)?

# Answer
> 3 votes
There are (at least) three algorithms that convert a regular expression to an equivalent finite-state automaton:

Büchi automata enter the picture if you are working with $\omega$-regular expressions. See e.g. this description of the algorithm for constructing an equivalent Büchi automaton from an $\omega$-regular expression.

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


title: Situation where FFD < BFD

text:
# Question
Title: Situation where FFD < BFD
I am practicing for an exam and one of the exercises is:

> Find an example sequence where FFD (offline) performs better than BFD (offline).

Intuitively I would say no such sequence exists as the sequence is sorted, but I have not managed to find a counterexample or proof.

# Answer
> 2 votes
Isn't *First/Best Fit Decreasing* always considered *offline* (requiring sorting the input assumed unsorted)?
Anyway, let me assume "performs better" to mean *uses less bins*.
I find it annoyingly hard to try to find an example using a minimum number of items, of item values and minimum item values - and to argue convincingly that it *is* minimal, but

> try a bin size of 16 and items of 11, 6, 6, 3, 2, 2, 2. Bin contents after adding each item:
> \- FF: 11 11,6 11,12 14,12 16,12 16,14 16,16
> \- BF: 11 11,6 11,12 11,15 13,15 15,15 15,15,2

---
Tags: algorithms
---


# Question
Title: Is there a different resolution of the "dangling else" problem other than "match closest"?
The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for `if expr then` and $b$ stands for `else` and $c$ stands for some other kind of instruction or block): $$ \begin{aligned} S &\rightarrow aSbS \\;|\\; aS \\;|\\; c\\ \end{aligned} $$ For example, $aacbc$ can be parsed as $(a(acbc))$ or as $(a(ac)bc)$ (this is the simplest/shortest ambiguous word for this grammar).

The "standard" way to resolve this "dangling else" ambiguity forces the "else" ($b$) statement to pair with the closest/innermost "if-then" ($a$). This can be accomplished as follows: $$ \begin{aligned} S &\rightarrow aTbS \\;|\\; aS \\;|\\; c\\ T &\rightarrow aTbT \\;|\\; c\\ \end{aligned} $$ This grammar is unambiguous. In the above example, it forces the $(a(acbc))$ parsing.

**Question:** Is there another natural way to resolve the ambiguity that would force the $(a(ac)bc)$ parsing of $aacbc$? In other words, I am looking for a grammar that generates the same language as the two above, that is unambiguous, and that parses $aacbc$ as $(a(ac)bc)$.

**Remark:** My first attempt was as follows: $$ \begin{aligned} S &\rightarrow aSbS \\;|\\; aU \\;|\\; c\\ U &\rightarrow aU \\;|\\; c\\ \end{aligned} $$ which resolves the ambiguity of $aacbc$ as required — but this grammar is still ambiguous: $aacbacbc$ can be parsed as $(a(ac)b(acbc))$ or as $(a(acb(ac))bc)$.

# Answer
This problem is an exact analogue of the problem of matching parentheses in an expression in which some of the close parentheses have been omitted. Here an "if" (or $a$ in the representative grammar) is an open parenthesis and an "else" ($b$) is a close parenthesis. (From the sequence of $a$s and $b$s you can mechanically insert $c$s by placing one before each $b$ and one at the very end.) Because it fits better with my parenthetic brain, I write as though that were the problem at hand.

The traditional "match closest" dangling-else resolution matches each close with the most recent as-yet-unmatched open. That means that there is never an unmatched open (or close, for that matter) between a matched open and its matching close.

One possible alternative would be to match each close with the earliest feasible unmatched open. "Feasible" here means that the open could be matched without violating parenthetic nesting (eg. the first $($ in $()()$ cannot feasibly match the last $)$).

This matching has to be done outside-in, so that a match for a close is not attempted until all the enclosing pairs have been matched. This fact makes it impossible to produce a parse with a bounded-lookahead algorithm, since the parse has to work inwards from both ends, after having split the string into completely matched segments (because those effectively limit the range of potential matches).

However, the fact that an online left-to-right parser doesn't exist does not imply that there is no unambiguous CFG. (Evidently: a palindromic language must be parsed from both ends towards the middle, but it's easy to write an unambiguous grammar).

To produce a grammar for the "furthest-match" parenthesis problem, I relied on the fact that an unmatched open cannot be followed by a matched open. If it were, then the furthest-match property wouldn't apply because the unmatched open could have matched the matched open's close, so the fact that it is unmatched violates the furthest-match property.

So here's the slightly clunky grammar:

$$ \begin{aligned} S&\to U \\;|\\; M \\ U&\to T \\;|\\; a U b T \\;|\\; a U b c \\;|\\; a M b U \\ M&\to a M b M \\;|\\; c \\ T&\to a T \\;|\\; a c \\ \end{aligned} $$

$S$ is the start symbol; $M$ are fully-matched statements; $U$ are definitely unmatched statements (which means they include at least one unmatched $a$, so they can't be empty) and $T$ is a "tail" consisting only of unmatched $a$s. The above fact about unmatched open's can be read directly from the grammar: all unmatched opens are derived from $T$, a $T$ can only appear at the end of a $U$, and a $U$ can only be followed by a $T$.

The clunkiness comes from preventing $U$ from matching the empty string. That prevents a bunch of what I consider spurious ambiguities: They are spurious in the sense that the matching of the opens and closes is the same in all alternative parses. If $U$ is allowed be nullable, it will also derive a completely balanced string. Since $S$ is, in effect, $M^\* U$, that leads to an ambiguity in which you could consider a completely-balanced $S$ to be a series of $M$ followed by an empty $U$, or one fewer $M$ followed by a completely balanced $U$.

Probably there's a better workaround than the one I chose. But this one seems to work, and it plays well with Bison's GLR parser which I used to test it; that parser complains about ambiguous parses unless you write extra code to handle the ambiguity, and I was too lazy to do that. I tested it with strings of up to 20 open+closes, and it seems to have produced an unambiguous parse for every correctly-nested sequence, without producing parses for incorrectly-nested sequences.
> 7 votes

# Answer
Take a+b+c+d+e and a-b-c-d-e. There are two obvious ways how a grammar could parse these, but there is one way that we use.

In the case of the "dangling else", that's not actually how people look at it. Instead the syntax is interpreted as "if", followed by zero, one or more "else if", followed by an optional "else".
> 0 votes

---
Tags: context-free, formal-grammars, parsers, ambiguity
---


# Question
Title: Efficient algorithm to check if a vector exists in the span of a subset of vectors
I have a binary vector $v \in \mathbb{F}\_2^m$ and a set of binary vectors $Q=\\{q\_1,q\_2,\dots,q\_n\\}$ each belonging to $\mathbb{F}\_2^m$ and I know that $v \in \text{span}\\{Q\\}$ but I want to know if there exists a subset $Q\_k \subset Q$ of at most $k$ vectors ( i.e. $|Q\_k| \le k \< n$ ) such that $v \in \text{span}\\{Q\_k\\}$. Is there a fast algorithm to do this other than the naive way of checking all the subsets of cardinality at most $k$? Assume that all of the operations are done in GF(2).

# Answer
> 1 votes
Equivalently, your problem can be stated as:

Given a $m \times n$ matrix $M$ over $\mathbb{F}\_2$ and a vector $v \in \mathbb{F}\_2^m$, find a vector $x\in \mathbb{F}\_2^n$ such that $M x=v$ and the Hamming weight of $x$ is as small as possible.

There are some hardness results for this problem. For instance, this post argues that the problem can't be approximated within a constant factor, within polynomial time (even for randomized algorithms), assuming standard complexity-theory assumptions.

See also https://cs.stackexchange.com/a/59922/755 and https://cstheory.stackexchange.com/a/10112/5038 and https://cstheory.stackexchange.com/q/27460/5038 and https://cstheory.stackexchange.com/q/10396/5038 for related work, including some algorithmic techniques that might be relevant.

---
Tags: algorithms, linear-algebra
---


title: What does the algorithm calculate?

text:
# Question
Title: What does the algorithm calculate?
We have the following

```
i <- 0
j <- 0
x <- 1
y <- 1
z <- 1
c <- 1
u <- 1
while i<n do
   i <- i+1
   j <- i
   x <- x*i
   z <- x
   y <- i+1
   y <- x*y
   while j<2*i do
      j <- j+1
      z <- z*j
   od
   c <- z div (x*y)
od

```

I want to find the loop invariant for both while-loops.

I applied the algorithm some times to understand what it does:

The inner while loop calculates the following: $$z=z\prod\_{m=1}^{2i-1}(i+m)=x\prod\_{m=1}^{2i-1}(i+m)$$ or not? Is this also the loop invariant of the inner while loop?

So I got the following results:

First loop:

```
i=1
j=i=1
x=1
z=x=1
y=i+1=2
y=x*y=2
inner while loop: z=x(i+1)=2
c = z div (x*y) = 2 div 2 = 1

```

Second loop:

```
i=2
j=i=2
x=1*2=2
z=x=2
y=i+1=3
y=x*y=2*3=6
inner while loop: z=x(i+1)(i+2)(i+3)=2*3*4*5
c = z div (x*y) = 2*3*4*5/2*6=10

```

Third loop:

```
i=3
j=i=3
x=2*3=6
z=x=6
y=i+1=4
y=x*y=24
inner while loop: z=x(i+1)(i+2)(i+3)(i+4)(i+5)=6*4*5*6*7*8
c = z div (x*y) = 6*4*5*6*7*8/6*24=5*7*8=280

```

Is everything correct? But what exactly calculates the algorithm? What is a general formula of the results?

# Answer
Note that $x=i!$. Now it's easy to see $y=(i+1)!$ and $z=(2i)!$. So $c=\frac{(2i)!}{i!(i+1)!}$, which is the $i$th Catalan number.

P.S. Your formula is wrong. The condition of the inner loop is $j=i+m\le2i$, so $m$ is from $1$ to $i$ instead of $2i-1$ or something.
> 2 votes

---
Tags: algorithms, correctness-proof, loop-invariants
---


# Question
Title: How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?
I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers:

```
void F3() {
    for (int i = 1; i < n; i++) {
        if (A[i-1] > A[i]) {
            swap(i-1, i)
            i = 0
        }
    }
}

```

It may not be clear, but here $n$ is the size of the array `A` that we are trying to sort.

In any case, the teaching assistant explained to the class that this algorithm is in $\Theta(n^3)$ time (worst-case, I believe), but no matter how many times I go through it with a reversely-sorted array, it seems to me that it should be $\Theta(n^2)$ and not $\Theta(n^3)$.

Would someone be able to explain to me why this is $Θ(n^3)$ and not $Θ(n^2)$?

# Answer
This algorithm can be re-written like this

1. Scan `A` until you find an inversion.
2. If you find one, swap and start over.
3. If there is none, terminate.

Now there can be at most $\binom{n}{2} \in \Theta(n^2)$ inversions and you need a linear-time scan to find each -- so the worst-case running time is $\Theta(n^3)$. A beautiful teaching example as it trips up the pattern-matching approach many succumb to!

*Nota bene:* One has to be a little careful: some inversions appear early, some late, so it is not per se trivial that the costs add up as claimed (for the lower bound). You also need to observe that swaps never introduce *new* inversions. A more detailed analysis of the case with the inversely sorted array will then yield something like the quadratic case of Gauss' formula.

As @gnasher729 aptly comments, it's easy to see the worst-case running time is $\Omega(n^3)$ by analyzing the running time when sorting the input $\[1, 2, \dots, n, 2n, 2n-1, \dots, n+1\]$ (though this input is probably not *the* worst case).

Be careful: don't assume that a reversely-sorted array will necessarily be the worst-case input for all sorting algorithms. That depends on the algorithm. There are some sorting algorithms where a reversely-sorted array isn't the worst case, and might even be close to the best case.
> 61 votes

# Answer
An alternative way of thinking about this is what the maximum value of `i` becomes before it is reset. This, as it turns out, makes it more straightforward to reason about how the prior sort order of `A` affects the run time of the algorithm.

In particular, observe that when `i` sets its new maximal value, let's call it N, the array `[A[0], ..., A[N-1]]` is sorted in ascending order.

So what happens when we add the element `A[N]` to the mix?

**The mathematics:**

Well, lets say it fits at position $p\_N$. Then we need $N$ loop iterations (which I'll denote $\text{steps}$) to move it to place $N-1$, $N + (N-1)$ iterations to move it to place $N-2$, and in general:

$$\text{steps}\_N(p\_N) = N + (N-1) + (N-2) + \dots + (p\_N+1) = \tfrac{1}{2}(N(N+1) - p\_N(p\_N+1))$$

For a randomly sorted array, $p\_N$ takes the uniform distribution on $\\{0, 1,\dots, N\\}$ for each $N$, with:

$$\mathbb{E}(\text{steps}\_N(p\_N)) = \sum\_{a=1}^{N} \mathbb{P}(p\_N = a)\text{steps}\_N(a) = \sum\_{a=1}^{N}\tfrac{1}{N}\tfrac{1}{2}(N(N+1) - a(a+1)) = \tfrac{1}{2} ( N(N+1) - \tfrac{1}{3}(N+1)(N+2)) = \tfrac{1}{3} (N^2-1) = \Theta(N^2)$$

the sum can be shown using Faulhaber's formula or the Wolfram Alpha link at the bottom.

For an inversely sorted array, $p\_N=0$ for all $N$, and we get:

$$\text{steps}\_N(p\_N) = \tfrac{1}{2}N(N+1)$$

exactly, taking strictly longer than any other value of $p\_N$.

For an already sorted array, $p\_N = N$ and $\text{steps}\_N(p\_N) = 0$, with the lower-order terms becoming relevant.

**Total time:**

To get the total time, we sum up the steps over all the $N$. (If we were being super careful, we would sum up the swaps as well as the loop iterations, and take care of the start and end conditions, but it is reasonably easy to see they don't contribute to the complexity in most cases).

And again, using linearity of expectation and Faulhaber's Formula:

$$\text{Expected Total Steps} = \mathbb{E}(\sum\_{N=1}^n \text{steps}\_N(p\_N)) = \sum\_{N=1}^n \mathbb{E}(\text{steps}\_N(p\_N)) = \Theta(n^3)$$

Of course, if for some reason $\text{steps}\_N(p\_N)$ is not $\Theta(N^2)$ (eg the distribution of arrays we're looking at are already very close to being sorted), then this need not always be the case. But it takes very specific distributions on $p\_N$ to achieve this!

**Relevant reading:**
> 9 votes

# Answer
**Disclaimer:**

This is not a proof (it seems that some people think I posted it as if it was). This is only a small experiment that the OP could perform to resolve his or her doubts about the assignment:

> no matter how many times I go through it with a reversely-sorted array, it seems to me that it should be $Θ(n^2)$ and not $Θ(n^3)$.

With such a simple code, the difference between $\Theta(n^2)$ and $\Theta(n^3)$ shouldn't be hard to spot and in many practical cases this is a useful approach to check hunches or adjust expectations.

---

@Raphael answered your question already, but just for kicks, fitting this program's output to $f(x) = a\cdot x^b + c\cdot x$ using this gnuplot script reported exponent values of $2.99796166833222$ and $2.99223727692339$ and produced the following plots (the first is normal scale and the second is log-log scale):

I hope this helps $\ddot\smile$
> 4 votes

# Answer
Assume you have an array.

```
array a[10] = {10,8,9,6,7,4,5,2,3,0,1}

```

Your algorithm does the following

```
Scan(1) - Swap (10,8) => {8,10,9,6,7,4,5,2,3,0,1}  //keep looking at "10"
Scan(2) - Swap (10,9) => {8,9,10,6,7,4,5,2,3,0,1}
...
Scan(10) - Swap(10,1) => {8,9,6,7,4,5,2,3,0,1,10}

```

Basically it moves to the end of the array the highest element, and in doing that it start overs at each scan effectively doing `O(n^2)` moves.. just for that one element. However, there are *n elements* so we'll have to repeat this `n` times. This isn't a formal proof, but it helps understand in an "unformal" way why the running time is `O(n^3)`.
> 3 votes

# Answer
The logic seems to be sorting the elements in the array in a ascending order.

Suppose the smallest number is at the end of the array(a\[n\]). For it to come to its right place - (n + (n-1) + (n-2) + ... 3 + 2 + 1) operations are required. = O(n2).

For a single element in the array O(n2) ops are required. So, for n eements it is O(n3).
> 0 votes

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


# Question
Title: Why not decide coNP language L with same NDTM used for $L^c$?
In Michael Sipser's book language is defined to be in NP iff it is decided by nondeterministic polynomial time Turnig machine. Why can't we use same machine to decide if language $L^c$ is in coNP? Just run every string x on same NDTM and if it accepts x then x is not in $L^c$ and if it rejects x then it is. What am I missing here?

In this book runnin time for NDTM is defind only for deciders, NDTM which halts in all branches.

# Answer
I assume that you want to "decide if $x\in L^c$ and output the complement". Tell me if I misunderstand.

$L^c$ is in NP if there's an NDTM accepts $x$ in "at least one" branch iff $x\in L^c$. So $x\in L$, i.e. $x\notin L^c$ means the NDTM rejects $x$ in "all" branches. Think more carefully about these quantifiers.

NDTM can always find the accepted branch if it exists, but this doesn't means the NDTM has checked all branches. So we can't decide if $x\in L$ with the same NDTM in the trivial way you mentioned.

Edit: If you want to prove $L\subseteq NP$, you should construct "one NDTM" such that there exists a polynomially long path to an accepting state iff $x\in L$. You might think flipping the answer is quite simple, but where's the answer? There doesn't even exist a state representing "NO". This is the problem. You can't add another Turing machine which read the output of $M$ and output its complement either since the whole structure is not a valid NDTM.
> 0 votes

---
Tags: complexity-theory
---


title: $\omega$-regular expression to LTL

text:
# Question
Title: $\omega$-regular expression to LTL
Is there any systematic (algorithmic) method to convert an $\omega$-regular expression like

$ (a^∗)(b)(b^∗)(a^∗)(c^\omega) $

to an LTL property?

# Answer
LTL is less expressive than $\omega$-regular expressions. For example, the expression $$((a+b)b)^\omega$$ i.e. "there is $b$ in all the even places" cannot be expressed in LTL.

In addition, observe that checking whether an $\omega$ regular expression is expressible in LTL is harder than checking universality, which is PSPACE hard.

However, there are ways to tackle this problem. You can start here for a reference.
> 3 votes

---
Tags: regular-expressions, linear-temporal-logic
---


# Question
Title: Is the optimal order of graph vertices s.t. minimizes edges to later vertices a well-known problem?
I'm a little unfamiliar with graph theory, and I found an interesting problem in my work that I do not know if its already well-known or can be easily mapped to another one. If I were to express the problem more formally:

Given a directed unweighted graph $\langle V,E \rangle$, find a total order between vertices $v\_1 \< v\_2 \< \dots \< v\_n$ such that minimizes $\vert F \vert$, where $F = \\{ \langle v\_i,v\_j \rangle \ \vert\ v\_i \< v\_j , \langle v\_i,v\_j \rangle \in E \\}$. That is find a total order between vertices such that it minimizes the number of edges that go "forward" in the order.

Lets suppose a simple directed graph:

The list of edges would be $\[ a \rightarrow b $, $b \rightarrow c$, $a \rightarrow c \]$.

A bad order would be $b \< a \< c$, because, for example, $c$ comes after $b$ in the order and we have the edge $b \rightarrow c $. Therefore, $F = \\{ \langle b,c \rangle , \langle a,c \rangle \\}$, $\vert F\vert = 2$.

A good order would be $c \< b \< a$, because $b \< a$ and $c \< b$. This gives $F = \emptyset$ and therefore the optimum: $\vert F\vert = 0$.

I have graphs that are dense, with some strongly connected components, and when trying to solve it using a SMT solver it works really bad with non-trivial instances. My intuition says that it's like a pigeonhole problem. So, my questions are:

* Is this a well-known problem in the graph-theory community?
* Can be easily mapped to any other problem?
* If so, there is any good algorithm to solve it?
* Can a good heuristic be computed easily?

Many thanks in advance :)

# Answer
Szymon Stankiewicz is right -- this problem is basically Feedback Arc Set, which is unfortunately NP-complete. But I have to mention that a very similar graph property, which goes by the slightly alarming name of *agony*, can actually be computed in just $O(m^2)$ time, where $m$ is the number of edges. The agony of a graph is essentially a weighted form of the size of the feedback arc set, in which we weight each violated arc by "how much" it is violated. Specifically, if we group the vertices into horizontal levels so that every downward edge has a penalty of 0 and every horizontal or upward edge has a penalty equal to one more than the number of levels crossed, the agony is the minimum possible penalty that could be produced by any such grouping.

See http://users.ics.aalto.fi/ntatti/papers/tatti14agony.pdf for the $O(m^2)$ algorithm, due to Nikolaj Tatti, which will construct an agony-minimising hierarchy. (Note that I myself have only read the abstract and enough to confirm that an actual hierarchy will be produced, not just the minimal agony score of one).
> 2 votes

# Answer
Your problem can be mapped to problem of finding minimal set of edges $F$ such that $G\backslash F$ is a DAG (each solution for your problem is a solution for this problem and vice versa). This problem is known as minimum feedback arc set problem and is one of Karp's 21 NP-complete problems
> 3 votes

# Answer
**Layered graph drawing**

Layered graph drawing is a graph in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. . However, graphs often contain cycles, minimizing the number of inconsistently-oriented edges is NP-hard, and minimizing the number of crossings is also NP-hard.

source: wikipedia : Layered Graph Drawing

your problem is strikingly similar to the problem of minimizing number of crossings:
> 1 votes

---
Tags: algorithms, graphs, smt-solvers
---


# Question
Title: How to find total number of minimum spanning trees in a graph with n edges?
I had this question on my final exam so sadly I don't have the question but as far as I remember, the question was saying:

> How many minimum spanning trees does a graph with 20 edges have.

I know that we can find minimum spanning trees with algorithms like Prim's algorithm etc. But how can we know the total number of minimum spanning trees in a graph with no figure given in the question (text only)?

# Answer
I'm hoping you misremembered the question, as the number of MSTs (minimum spanning trees) is not uniquely determined by the number of edges. It depends on what edges are and are not present and also what their weight's are.

For example, if the graph has 21 vertices and 20 edges, then it is a tree and it has exactly one MST. On the other hand, if it has seven vertices and 20 edges, then it is a clique with one edge deleted and, depending on the edge weights, it might have just one MST or it might have literally thousands of them.

(A clique on seven vertices has 21 edges, which is only one more than your graph is allowed. If all the edge weights were the same, every subtree would be an MST and, by Cayley's formula, there are $7^5=16807$ different trees with seven vertices.)
> 3 votes

# Answer
You cannot know that if the number of edges is the only information you have. It would minimally require a global layout of the graph (thus, edge weights and which nodes are connected) to solve.
> 1 votes

---
Tags: graphs, spanning-trees
---


# Question
Title: Can there be an algorithm for a relation which is not a function?
Functions are relations but all relations may not be functions.Can there be an algorithm for a relation which is not a function?What has theory of computation got to say about relations in general.

# Answer
> 3 votes
Your question is very general, especially it is not clear to me what you mean by "algorithm for a relation". I still have some answers.

The difference between (binary) relations and functions is that the former can have several different outputs for the same input. This is just what *non-determinism* offers us. Thus the theory of computation offers us many models of computation thatcan be seen as computing relations instead of functions.

Further, the input in the most common models of computations has the form of a string. Thus you could compute a relation in the way that string "(x,y)" is accepted iff (x,y) forms part of the relation. This, of course, generalizes to relations of higher order.

# Answer
> 2 votes
This question is not very clear. Let us assume you are asking about calculating *inputs* from *outputs* in case of relations. Consider a relation $R \subseteq A \times B$ is a relation between inputs of type $A$ and outputs of type $B$. There are several possibilities for the meaning of "algorithm $\rho$ computes $R$":

1. For every $x \in A$, $\rho(x)$ outputs *some* $y \in B$ such that $R(x,y)$. If there is no such $y$ then $\rho(x)$ may be undefined. We may think of $\rho$ as a computable *selection* or a *choice* function for $R$, because it *chooses* for every $x \in A$ some $y \in B$ such that $R(x,y)$.
2. For every $x \in A$, $\rho(x)$ outputs *all* $y \in B$ such that $R(x, y)$. Here we need to answer how the set $\\{y \in B \mid \rho(x,y)\\}$ is represented. If we know that there are finitely many such $y$, then we can just list them all. But in general this is going to be a complicated question.

Let us do an example. Consider the case where $A$ is the set of polynomials, $B$ is the set of real numbers and $R(p,x)$ is defined as $p(x) = 0$. That is, a polynomial $p$ is in relation $R$ with a number $x$ when $x$ is a root of $p$. Then:

1. In the first case $\rho(p)$ must calculate one root of $p$, if it exists.
2. In the second case $\rho(p)$ must calculate the list of *all* roots of $p$.

---
Tags: computability, automata
---


# Question
Title: Efficient algorithm to find number of sequences in string
Suppose I have a string that goes like "abcabcdeaabcdef", where each character is either one more than the previous one or a.

If the character at position i is "c", I know that it is preceded by "ab".

I want to find the number and length of all sequences (substrings that contain sequential characters). For example, the above string would give "abc", "abcde", "a", "abcdef".

Is there a more efficient algorithm to do this than simply doing a O(n) search over the string?

# Answer
You cant create an algoithm to do this in the worst case. Even if we read right to left and if we assume we can do some level of jumping (e.g if we see an f we can jump 6 spaces left) we still have to, in the worst case (the string of a's), read over the entire string. This can never be done in $o(n)$ time. The right to left with skipping will run in $O(m)$ time where $m$ is the number of increasing subsequences, and $m$ is $O(n)$.
> 2 votes

# Answer
Hmm i don't think so.Let's suppose there exists algorithm which does less then (n-2) comprehensions and gives a correct answer. (we assume we never get empty input and our input always starts with a thats why n-2)

Let's define 2 inputs A = aaaaaaa... and B = aaa....b...a.aaa

Of course f(a) = n and f(b) = n - 1 where f is our algorithm.

Let's play a game with our Alghoritm:

Let's define function g(x) = 1 if input\[x\] = a, 0 otherwise.

Each call to g is one comprehension. We can easily construct 2 inputs with different numer of sequences which would have identical result of n-2 calls of g
> 0 votes

---
Tags: algorithms
---


title: Evaluating tree data iteratively

text:
# Question
Title: Evaluating tree data iteratively
Community,

I'm working on a project lifting assembler code to a AbstractSyntaxTree-like structures like these:

In order to be able to evaluate the final value of a tree given only leafes with constant values, I implemented an recursive approach: Each node class has its own *value* function. For all nodes except constants, it will query the *value* function of its children.

e.g. A add node has a value function which works like this:

```
self.children[0].value() + self.children[1].value()

```

This seems simple and stores Operation-Logic where it belongs: into operation nodes. The main problem is that these trees tend to be become very large and I fear an recursive approach might not be the best way here.

The most common operations ran on this tree are tree merging and optimization (transversal + modification). At the moment we use single-linked notes, since this serves the use cases in the best way.

Is there any iterative way of archiving this value evaluation? Any help appreciated.

# Answer
> 1 votes
A recursive function is only bad if it ends up repeating work and in this case it does not have too. A postorder traversal of the tree is what you want to do here, and the iterative solution exists, but is considerably more difficult to implemant. A post order traversal will only visit each node once, and you will not beat that for complexity.

---
Tags: trees, recursion, graph-traversal
---


# Question
Title: How to select a subset of columns in a given matrix to satisfy a condition?
Let $a\_{kn}$ be positive real numbers for all $k\in\\{1,\dots,K\\}$ and $n\in\\{1,\dots,N\\}$ and let $t\>0$. I need to find a subset $S$ of $\\{1,\dots,N\\}$ of minimum size such that:

* if $|S|=1$ then $a\_{ki}\geq t$ for all $k\in\\{1,\dots,K\\}$ and $i\in S$.
* if $|S|\>1$ then for all $k\in\\{1,\dots,K\\}$, there must exist some $i\in S$ such that $a\_{ki}/a\_{kj}\geq t$ for all $j\in S\backslash\\{i\\}$.

I need to find a good heuristic for this problem (an optimal if possible).

*Example*:

* let $t=2$; and
* the matrix $A$ given as:

$$A=\begin{pmatrix} 50 & 1 & 1\\ 1 & 70 & 1\\ 1 & 1 & 40\end{pmatrix}.$$

The set $S$ should be $\\{1,2,3\\}$.

To solve the problem, I need to enumerate all possible subsets of $\\{1,\ldots,N\\}$. Do you see any particular characteristic of the problem that I can use to solve it?

# Answer
> 3 votes
The feasibility version of your problem is NP-complete, for any fixed $t \> 1$, by reduction from SAT.

Suppose we are given a formula over the variables $x\_1,\ldots,x\_a$, having clauses $C\_1,\ldots,C\_b$. We will have $2a$ columns, one column per literal.

For each variable $x\_i$ we will have the following row:

* Positions $x\_i,\lnot x\_i$ have value $1$, and all other columns have the value $1/t$.

This row forces the solution $S$ not to be a singleton, and forces it to contain exactly one of $\\{x\_i,\lnot x\_i\\}$.

For each clause $C\_j = \ell\_1 \lor \cdots \lor \ell\_c$ we will have the following row:

* Positions $\ell\_1,\ldots,\ell\_c$ have values $1,1/t,\ldots,1/t^{c-1}$, and all other positions have value $1/t^c$.

This row forces the solution to contain at least one of the literals $\ell\_1,\ldots,\ell\_c$.

Conversely, any satisfying assignment corresponds to a set $S$, as can be easily checked. Hence a set $S$ exists iff the original formula is satisfiable.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Average case complexity of search data structures
Algorithms are generally studied in terms of average case complexity and worst case complexity? Is there also a kind of analysis called "average worst case" complexity?

# Answer
> 2 votes
One such notion is that of smoothed analysis, in which we compute the worst-case expected complexity of an algorithm on a randomly perturbed input. In more detail, let $N(x)$ be a randomly perturbed version of $x$, and let $T$ be the time complexity of the algorithm. Then we are interested in $$ \sup\_x \mathbb E\[T(N(x))\]. $$ The "worst case" aspect is with respect to the unperturbed input, and the "average case" aspect is with respect to the perturbation.

The simplex algorithm has been shown to be polynomial time in this sense, although its worst case complexity is exponential.

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


# Question
Title: Trouble Replicating Proof of The Lambda Calculus Fixed Point Theorem
From pg. 35 of *Lambda Calculus and Combinators An Introduction*:

> **Corollary 3.3.1** in $\lambda$ and $CL$: for every $Z$ and $n \ge 0$, the equation
>
> $$ xy\_1 \ldots y\_n = Z $$
>
> can be solved for $x$. That is, there is a term $X$ such that
>
> $$ Xy\_1 \ldots y\_n =\_{\beta, w} \[X/x\]Z. $$
>
> *Proof:* Choose $X \equiv \mathsf{Y} (\lambda x y\_1 \ldots y\_n.Z)$.

Note: In the book, we assume that $\mathsf{Y} \equiv (\lambda ux. xuux)(\lambda ux. xuux)$. Further, for ease of notation, let $V \equiv (\lambda x y\_1 \ldots y\_n.Z)$.

The problem is that when I check this with my own examples, I'm not getting this result.

For example, suppose that neither $x$ nor any of $y\_1, \ldots , y\_n$ is in the free variables of $Z$ (to make it easy). Then this theorem asserts that if $X \equiv \mathsf{Y}(\lambda x y\_1 \ldots y\_n . Z)$, then

$$ Xy\_1 \ldots y\_n =\_{\beta, w} Z $$

When I check whether this true, I get

$$ (\mathsf{Y}(\lambda x y\_1 \ldots y\_n . Z))y\_1 \ldots y\_n = (\mathsf{Y}V)y\_1 \ldots y\_n = (V\mathsf{Y}V)y\_1 \ldots y\_n =\_{\beta, w} Zy\_n $$

Am I doing something wrong?

# Answer
> 1 votes
$\newcommand{\Y}{\mathsf{Y}}$

Did you leave out any parentheses by any chance? We should take $\Y = (\lambda u x . x (u u x)) (\lambda u x . x (u u x))$. Note that $x u u x$ is the same as $(x u u) x$, which is *not* the same as $x (u u x)$.

We use the abbreviations $V = (\lambda x y\_1 \ldots y\_n . Z)$ and $X = \Y V$, as in your question. Then we calculate: \begin{align\*} \Y V &= (\lambda u x . x (u u x)) (\lambda u x . x (u u x)) V \\ &= (\lambda x . x ((\lambda u x . x (u u x)) (\lambda u x . x (u u x)) x)) V \\ &= V ((\lambda u x . x (u u x)) (\lambda u x . x (u u x)) V) \\ &= V (\Y V) \end{align\*} and hence \begin{align\*} X y\_1 \ldots y\_n &= \Y V y\_1 \ldots y\_n \\ &= V (\Y V) y\_1 \ldots y\_n \\ &= (\lambda x y\_1 \ldots y\_n . Z) (\Y V) y\_1 \ldots y\_n \\ &= (\lambda x y\_1 \ldots y\_n . Z) X y\_1 \ldots y\_n \\ &= \[X/x, y\_1/y\_1, \ldots, y\_n/y\_n\] Z \\ &= \[X/x\] Z. \end{align\*}

---
Tags: lambda-calculus, combinatory-logic
---


title: The ultimate virtual machine

text:
# Question
Title: The ultimate virtual machine
It seems to me that one way computer science could be divided up, is into three domains:

1. What is efficient for humans to represent and comprehend
2. What is efficient for computers to represent and process
3. An idealized form of how computation/problems are defined that is extremely succinct, specific, and not tied to human or computer limitations

What I am most interested in, is this third domain. I believe if a lot of effort is invested there, it will drive the advancement of the other two domains.

Towards that end, I am interested in the development of an "ultimate" virtual machine. Something with a gratuitously minimal and impoverished grammar, and an extremely advanced type system.

I am wondering if anything like this exists. I am also trying to develop something like this, with the idea that it doesn't.

# Answer
I have not heard of any computational problem that cannot be solved by an Universal Turing Machine, and UTM itself fits on a single page:

https://rosettacode.org/wiki/Universal\_Turing\_machine

In accordance with your plan, it totally disregards human and hardware limitations, by using up both time and space extravagantly. If you disregard some limitations, the quality of an answer quickly degrades to the point of being irrelevant.

IMHO the art of computing is in seeing the equivalence classes and transforming some initial solution to re-balance resources for the specific prioritized objectives. In the absence of priorities and limitations, there is no art. This quest is provably inexhaustible and will never be possible to automate.

BTW, I am also working on a new computing platform (a CPU and a programming language) that is an order-of-magnitude better in one aspect (speed, low transistor count, low energy consumption, easy comprehensibility, short programs), while matching existing solutions on the other aspects. It is a synergy based on closer matching the actual problem and balancing the workload among transistors, microcode and high-level-code. I see a big unused slack in the current technologies, and the gains can be spent on the mentioned objectives.
> 2 votes

---
Tags: programming-languages, language-design
---


# Question
Title: How to prove a greedy algorithm that uses the longest increasing subsequence?
Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy algorithms.

The problem says: I need to sort an array of $n$ numbers, but the only operation I am able to do is to move an element from position $i$ to $j$, and if $i\<j$ then every elements in the interval $\[i+1, j\]$ (inclusive) are moved one position backwards. On the other hand if $i\>j$ then every element in the interval $\[j, i-1\]$ increase their position by one. That operation has a cost of $i+j$ for doing it. So I need to sort the array using the lowest cost possible using a series of only that kind of operations.

Assume that I need to sort the array in *decreasing order*.

After a lot of thinking, I came up with the idea of finding the (first) **longest increasing subsequence from right to left**. If I have that sequence, we are to assume that those elements in that sequence are already sorted. So, I wouldn't need to use them (i.e selecting them (from $i$) to move them (to $j$)), cause they are already sorted. That way, the cost of moving them would never be calculated into the final cost of making every operations. And also I will be doing fewer operations and then guaranteeing that the ones I am doing has the lowest cost.

The cost will be easily calculated because the subsequence was created using a sort of **Tuple** element, with the value and the actual position in the array, so I'll use the value of the position to calculate cost.

After having that subsequence in hand, I am to insert the remaining elements in that sequence (the first longest increasing subsequence from right to left). After that I insert the remaining elements in a **Queue** to easily **Dequeue** them in the order of their position (from lowest to highest). That way, we guarantee that the cost of moving them will be minimum. After inserting we update the position of the elements in the sequence (in the **Tuple**) in the **Queue** and in the sequence (say I am using a **List** of **Tuple** for the sequence).

That algorithm is working, and have thrown a correct answer for several cases I tested against a brute force algorithm version.

Now I need to proove it works, but I have no clue how. It can easily be seen I am using a greedy aproach to insert the elements, but I how does it guarantee what I am looking for!

Hope anyone can point me into the right direction of that proof! Thanks in advance

**EDIT:** I have done some progress here, and I am in a point where I have proven that the optimum must have selected a decreasing subsequence to avoid those items of being moved, but I need to prove that this is the maximum decreasing subsequence. In order to do that I am trying to prove that the cost of moving $X$ elements is less than the cost of moving $Y$ elements with $X\<Y$. I haven't been able to prove it, but I can't come up with an example that prove me wrong.

Do you think this happens? How could I prove it?

Thanks

**EDIT:** This is the problem itself SPOJ Problem RSORTING - RANKLIST SORTING I have a solution but I need to prove its correctness

# Answer
> 1 votes
The most intuitive way to prove such an issue, where you're ordering elements by rank in a list, is to use an **exchange argument**. In short, it comes down to proving that whenever an inversion exists in the list, your algorithm inverts them so that they become ordered correctly. By proving this to be the case for every value/index pair it follows naturally that the list ends up completely ordered.

Many universities have publicly available courses on the matter. For example the TU Delft has an excellent Open CourseWare page on algorithmics that includes the subject, to be found at:

https://ocw.tudelft.nl/course-lectures/3-greedy-algorithms/

---
Tags: sorting, proof-techniques, correctness-proof, greedy-algorithms
---


# Question
Title: When is a first-order formula is existential and when is it universal?
So I have a few questions about determining which formula it is:

So if a binary predicate symbol $X$ denotes an edge between two variables, say $x$ and $y$, for the following formulas

* Why is $\forall x \exists y\\,(X\[xy\]\lor X\[yx\])$ universal and $\exists x \forall y\\,(X\[xy\]\lor X\[yx\])$ existential? I mean for the second formula all $y$ are within the scope of $\forall y$, so shouldn't it be universal as well?
* And if you have a formula like this: $(\exists x X\[xy\]) \odot X\[yx\]$, where $\odot$ denotes an arbitrary binary connective, would this be a binary connective formula or an existential formula?

Thanks.

# Answer
> 1 votes
The key to the usage is to transform the formula to an equivalent formula that is in *prenex form*.

A formula $F$ is in *prenex form* if $F \equiv Q\_1 x\_1 ...Q\_m x\_m\\; G$ where $G$ is a quantifier free formula and $Q\_1,...,Q\_m$ are quantifiers.

A formula $F$ is universal if it is equivalent to a formula in prenex form that has only universal quantifiers.

There is an important model theoretic property of universal formulas: a universal formula that is satisfiable in some structure $S$ is also satisfiable in any substructure $P$ of $S$.

> Why is $\forall x \exists y(X\[xy\]∨X\[yx\])$ universal and $\exists x \forall y(X\[xy\]∨X\[yx\])$ existential? I mean for the second formula all $y$ are within the scope of $\forall y$, so shouldn't it be universal as well?

Either sentence is neither universal nor existential. One can easily come up with an example structure where $F\equiv\forall x \exists y(X\[xy\]∨X\[yx\])$ is true but is not true for a substructure.

> Let $S=\\{0,1\\}$ and $X\[xy\]\equiv x\not=y$, then F is true in $S$ but is not true for any one-element substructure of $S$.

Now for the second question

> And if you have a formula like this: $H\equiv(\exists x X\[xy\])⊙X\[yx\]$, where ⊙ denotes an arbitrary binary connective, would this be a binary connective formula or an existential formula?

In order to find the prenex form we rename the variable $x$ in the scope of the existential quantifier to get $H'\equiv(\exists z X\[zy\])⊙X\[yx\]$.

Now suppose $⊙$ is disjunction or conjunction then we can consider an equivalent formula $H''\equiv\exists z X\[zy\]⊙X\[yx\]$ that is in prenex form and is an existential formula.

However if $⊙$ were an implication then the formula $H$ would be equivalent to $H'''\equiv\forall z X\[zy\] \Rightarrow X\[yx\]$. The formula $H'''$ is clearly a universal formula.

# Answer
> 0 votes
> why is AxEy(X\[xy\]vX\[yx\]) Universal and ExAy(X\[xy\]vX\[yx\]) existential?

The first formula translates to:

"For all x, there exists a y such that..."

The second formula translates to:

"There exists an x for which all y..."

In other words, the outermost denominator determines whether the formula is universal or existential (if it has a global scope). As you can see above, interchanging the place of the quantifiers changes the meaning of the formula.

> I mean for the second formula all y are within the scope of Ay, so it should be universal as well??

The formula states that there exists an x for which all y (within that subset) share a property, not that all y in the universe share that property.

> And if you have a formula like this:
>
> > (Ex X\[xy\]) V (X\[yx\]),
>
> where V denotes a binary connective, would this be a binsary connective formula \>or an existential formula?

Essentially, this formula isn't necessarily existential or universal since there is no shared global scope.

What it translates to (if for example we take V to be OR) is:

"There exists an x which has an edge between x and y OR there is an edge between y and x".

To answer the question; this is a combination of two formulas, the first of which is existential (denoted by the E) and the second of which is atomic with a truth-value that is determined by the meaning of x and y (as they are free variables since they do not fall under the scope of a quantifier).

---
Tags: logic, first-order-logic
---


# Question
Title: Do formulas involving fewer repetitions of variables give higher numerical precision?
I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis.

> Exercise 2.15. Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, `par2` is a "better" program for parallel resistances than `par1`. Is she right? Why?

This question is a little confusing when pulled out of context, so please let me explain. The formula for parallel resistors can be written in two algebraically equivalent ways: $\frac{R\_1R\_2}{R\_1+R\_2}$ and $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$. However, it seems that computing parallel resistors with the second formula would always produce higher precision than using the first one.

My question is:

1. Which formula is better? $\frac{R\_1R\_2}{R\_1+R\_2}$ or $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$? Here "better" means provides higher precision.
2. Why it is better than the other one? Please prove your answer to the first question.

---

Here is my effort

> After many experiments, $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$ seems to be the better formula. I guess that the reason behind can be conclude as *the fewer time uncertain numbers are repeated, the less uncertainty is introduced, and the higher precision we can get.*

But that's not enough. I expect a more scientific and more rigorous answer.

# Answer
First, I want to say that it is *not* the case in general that an algorithm that minimizes the number of uses of the inputs is more accurate, at least for IEEE 754 floating point. For example, compensated summation.

On the other hand, it's certainly the case that interval arithmetic can *greatly* benefit from knowing when two inputs are identical. As a trivial example, if $X$ is an interval variable, then logically $X - X = 0$ but of course the subtraction algorithm (usually) doesn't know whether it's inputs are logically identical, and so it must assume the worst-case $$X - X = \[X^{lo} - X^{hi},X^{hi} - X^{lo}\]$$

This is roughly what's going on here and almost certainly view SICP is taking. If you use naive interval arithmetic operations, repeated uses of a variable will be treated independently, and so it won't be possible to cancel out error and the worst-case must be assumed. Using the formulas from the interval arithmetic Wikipedia page and assuming $R\_1$ and $R\_2$ are represented by intervals that are strictly positive, you can simply calculate: $$\frac{1}{\frac{1}{R\_1}+\frac{1}{R\_2}} = \left\[\frac{1}{\frac{1}{R\_1^{lo}}+\frac{1}{R\_2^{lo}}},\frac{1}{\frac{1}{R\_1^{hi}}+\frac{1}{R\_2^{hi}}}\right\]$$ while $$\frac{R\_1 R\_2}{R\_1 + R\_2} = \left\[\frac{R\_1^{lo}R\_2^{lo}}{R\_1^{hi}+R\_2^{hi}},\frac{R\_1^{hi}R\_2^{hi}}{R\_1^{lo}+R\_2^{lo}}\right\]$$

It's clear that $$\frac{R\_1^{lo}R\_2^{lo}}{R\_1^{hi}+R\_2^{hi}} \leq \frac{R\_1^{lo}R\_2^{lo}}{R\_1^{lo}+R\_2^{lo}}$$ and symmetrically for the upper bounds, so the latter formula has a looser interval.
> 4 votes

---
Tags: algorithms, proof-techniques, computation-models, mathematical-analysis, numerical-analysis
---


# Question
Title: How does MCTS handle games with large numbers of poor moves?
I am trying to understand how pure Monte Carlo tree search (https://en.wikipedia.org/wiki/Monte\_Carlo\_tree\_search) handles games where random playout will likely result in a loss easily avoided by other types of agents.

For example, imagine a hypothetical game with a single player. At game start, the player can choose between move A or move B.

Move A results in a fair coin flip that determines win/loss.

Move B results in a second set of 10 possible moves for player A, one of which is a win (move C, let's call it), and the other 9 a loss.

Random playout will have move A winning 50% of the time, and Move B winning 10% of the time, even though the ability to always pick the winning move B-\>C is within the player's power.

Can MCTS handle games of this nature well? How does it do so?

Obviously this toy example can trivially be solved by other search methods, but the real game I'm interested in has a prohibitive branching factor for things like depth- or breadth-first search, and a proper evaluation function is difficult.

# Answer
> 3 votes
Issues like these are essentially solved in the MCTS itself. The principle of the algorithm is that it tries to make the best pick, rather than guaranteeing it (if done in this randomized fashion rather than a 'pure MCTS' fashion). The trees are built up out of large amounts of collected data, aggretating success rates in the nodes. Nodes that end up being succesful more often will have a larger likelihood of being picked. This process of positive reinforcement means that nodes that always lead to a victory will, over the course of many playthroughs, approach a 100% pick rate.

In your example, node A will have a rougly 50/50 success/failure ratio throughout any number of playthroughs (due to the coinflip). Node B will have a 10/90 ratio of success/failure at first but will approach a 100/0 ratio as the number of playthroughs nears infinity (node C will end up always being picked due to the 100% success rate, and this propagates to node B).

The result is that node B will gradually end up being picked more often than node A, reinforcing the effect and causing it to be picked even more often.

The image on the wikipedia page illustrates it very well; the nodes with a high chance of success gradually make up a larger fraction of the total 'node weight' on a level, thus increasing the odds that it is picked with every playthrough.

---
Tags: board-games, monte-carlo
---


# Question
Title: Proving $a^{2+n}a^{n}$ is regular using the Pumping Lemma
So I'm trying to practice (and learn, clearly) use of the Pumping Lemma, and this is my current equation. It's clearly regular- it can be simplified:

$a^{2+n}a^{n} = a^{2+2n}$ and from there it's fairly easy to derive the regular language $aa(aa)\*$

However, I'm trying to explicitly solve this through the Pumping Lemma- but clearly doing something wrong. This is my process (assuming language $A$, string $s$ in $A$, pumping length $p$):

First take $s = aaaa$ for $n = 1$ (simple case).

Take $p = 2$, and so $xy$ must equal $aa$ to fit $|xy| \leq p$ and $|y| \gt 0$ , giving $x = a, y = a, z = aa$.

Finally insert into the equation $xy^{i}z \in A$ with a trivial value of $i \geq 1$ - $xy^{2}z$. This gives a result of $aaaaa$.

And that's the problem. $aaaaa$ is not a member of the language $a^{2+n}a^{n}$. Is there a step I'm missing here or a wrong assumption?

Thanks. And apologies for yet another pumping-lemma question.

# Answer
<sup>**Noooooo!**</sup>

Usage of the pumping lemma to prove regularity is remarkably rare, and certainly won't happen with a direct application.

Let's review the formal statement, with particular emphasis on the quantifiers:

$$\forall \ L \subseteq \Sigma^\* ( \ L \ \text{is regular} \Rightarrow \exists \ p \ge 1 \ \ \forall \ w \dots \ \ \exists \ x, y, z \dots \ \ \forall \ i \dots \ )$$

Two notable observations are that *being regular is part of the hypotheses* and that *nothing is said about the converse, which is in fact false* (a number of classical counterexamples can be found in literature).

In other words, even if you managed to somehow prove the $\exists \forall \exists \forall$ block, it still wouldn't say anything about the regularity of $L$. The way the pumping lemma is normally used is in its *contrapositive* form. You may recall from basic logic that $(p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p)$. Using that principle, we can derive the following logical consequence:

$$\forall \ L \subseteq \Sigma^\* ( \ \forall \ p \ge 1 \ \ \exists \ w \dots \ \ \forall \ x, y, z \dots \ \ \exists \ i \dots \Rightarrow L \ \text{is }\textbf{not }\text{regular} \ )$$

Notice how this is a tool to prove *non-regularity*, and that, even there, nothing can be said about the converse.

I'm afraid your attempt of proof is just entirely misguided.
> 5 votes

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


# Question
Title: Is there any way to "pre-compute" a huge dataset in order to make *any* arbitrary linear-time computation on it sub-linear?
Suppose that you have a huge (terabytes worth) collection of numbers, and you know that you will, in a future, need to run some statistics of it. In order to cut future work, you notice that, by pre-computing some key statistics, you can make other statistics be computable in sub-linear time. For example, if you store the `sum` and the `length` of the collection, you can, in a future, compute the `average` in linear time. If you also store the `variance`, you can compute the `standard deviation`. You can keep adding specific statistics in hope to cover as many "future computations" as you could.

My question is: is there any way to prepare the dataset such that any arbitrary linear-time function could, in a future, be processed in sub-linear time? In other words, is the snippet below possible?

```
# builds an ideal pre-computation of an arbitrary bit string
precomputed = precompute(arbitrary_bit_string)

# builds a circuit for a "countOnes" function
# could be any other arbitrary linear-time function
countOnes = buildCircuit("... an String->Int algorithm here ...")

# computes the number of ones in sub-linear time
average = execute(precomputed, countOnes)

```

# Answer
Multiplying the size of the dataset you have to pre-calculate over does not increase the amount of time it takes to calculate the average when the sum and length are pre-calculated; it will be a constant time operation. Moreover, calculating the sum and length of a dataset in itself is only linear time (doubling the dataset will result in doubling the amount of time it takes to pass over all data and therefore is only linear, the 'addition' operation is constant-time and does not contribute to the time complexity).

However, I think what you meant is the following:

If I had any possible data readily accessible, would that mean I can run a more optimal algorithm over this new dataset than I could over the original dataset?

The answer is no.

Some examples:

* The original dataset contains 10 integers. We want to calculate the total when we multiply each number by every other number. This is an O(n^2) algorithm since for each element we have to pass over all other elements. If we had precalculated the set resulting from multiplying each number by all other numbers it would only take linear time; O(n) since we only have to sum the numbers in the dataset. So for this function the hypothesis holds.
* The original dataset contains 10 integers. We want to calculate the sum of the first two numbers. This will take O(1) time, as the size of the dataset does not increase the time it takes to sum the first two numbers. Now assume that we had precalculated this value then it would still be an O(1) algorithm. After all, no (0) time is still considered constant time.
* The original dataset contains 10 integers. We want to know the value at the first index. This is obviously a constant time O(1) function and, as a result, one that cannot be done more efficiently regardless of any precalculated data.

P.S. do note that this is only the purest sense that it does not hold for every function; it might very well be that every real-world application can more efficiently be run over a set containing pre-calculated data).
> 1 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Can we use exponential function in a reduction?
If I have an NP-complete graph problem $P1$ whose instance, say, a graph $G$ and a positive integer $k$ and I have another graph problem $P2$ whose instance is a graph $G'$ and a positive integer $k'$. I would like to prove that $P2$ is NP-complete. The reduction is as follows:

* set $G'= G$ and
* set $k'= f(k)$.
* $P1$ is solved iff $P2$ is solved.

My question is: is this reduction correct when $f(k)$ is exponential function?, For simplicity, say, $f(k)=2^k$. I am afraid that this is no longer polynomial-time but then again calculating $2^k$ or $k!$ is polynomial-time problem.

My whole question is general as the title mentions: Can we use exponential function in a reduction to create some parameter in the instance of the concerned problem?

**EDIT**

My question is motivated by the validity of using exponentiation in polytime reduction on cstheory.SE where the OP asks about a specific reduction used in some paper. My question is general about using exponentiation in reduction.

# Answer
For the sake of notation, I'm going to assume you're trying to produce a polynomial time reduction $f$, which that maps instances $x$ of some problem $L\_1$ to instances $f(x)$ of some other problem $L\_2$. Instances of $L\_i$ have parameter $p\_i$ ($i\in\\{1,2\\}$). Since the reduction has to run in polynomial time, it has to output at most a polynomial number of bits, say $|x|^q$ for some constant $q$. In particular, the representation of $p\_2$ can't be more than $|x|^q$ bits long.

So, suppose the value of the parameter is $k$ in some instance $x$ with parameter $p\_1=k$. Whether or not $f(x)$ can have parameter $p\_2=2^k$ depends entirely on what the parameters are and how big $p\_1$ can be.

If $p\_1$ is a number represented in unary, we have $p\_1\leq |x|$; if it's a number represented in binary or some higher base, then $p\_1 = O(2^{|x|})$. If $p\_1$ is the size of some object described in $x$, then its size will depend on what kind of object it is (e.g., if $p\_1$ is the size of some set of a graph's the vertices, $p\_1\leq |x|$; if it's the number of pairs of vertices with some property, $p\_1\leq |x|^2$, and so on).

And, now, what's $p\_2$? If it's a number in unary, then $2^k$ is a string of length $2^k$, so we need $2^k\leq |x|^q$, i.e., $k=O(\log |x|)$. If it's a number in binary, then $2^k$ is just a $1$ followed by $k$ zeroes, so we can write this in our output as long as $k=O(|x|^q)$. If it's the size of some structure then, again, it depends on how that structure is represented. For example, if you need to add $2^k$ vertices, you need all those vertices to be stored in at most $|x|^q$ characters, so $k$ had better not be any bigger than about $\log n$.
> 7 votes

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


# Question
Title: Time complexity of functions that call each other
I'm having trouble reasoning about the time complexity of these mutually recursive functions. This was asked on SO here but the answer there didn't help me. I tried substituting one of the recurrences in the other but because they are mutually recursive I got stuck. I tried writing out the function calls for x=10 but I'm stuck making sense of that too. How do I go about working through something like this?

```
int foo(int x)
{
  if(x < 1) return 1;
  else return foo(x-1) + bar(x);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

```

Edit: With @quicksort's answer I get S(n) = 2\*S(n-1) + S(n/2) - S(n/2-1) and if I try to solve it using Wolfram I'm seeing something different: solution . Also, it's not intuitive to me that this is exponential. How does one see that?

# Answer
> 1 votes
Let $\mathcal{S}(n)$ be the running time of `foo` and $\mathcal{T}(n)$ be the running time of `bar`. We have the following system of recursive equations:

$$ \left\\{ \begin{array}{r c l} \mathcal{S}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n/2) + \Theta(1) \end{array} \right. $$

By isolating $\mathcal{T}(n)$ in the first and $\mathcal{S}(n)$ in the second, we obtain:

$$ \left\\{ \begin{array}{r c l} \mathcal{S}(n-1) & = & \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n) - \mathcal{S}(n-1) + \Theta(1) \end{array} \right. $$

I will now solve for $\mathcal{T}$, with a similar reasoning holding for $\mathcal{S}$. Since:

$$ \mathcal{S}(n-1) = \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1) $$

We also have that:

$$ \mathcal{S}(n) = \mathcal{T}(n+1) - \mathcal{T}((n+1)/2) + \Theta(1) $$

Therefore the first equation of our original system becomes:

$$ \mathcal{T}(n+1) - \mathcal{T}((n+1)/2) = \mathcal{T}(n) + \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1) $$

Reordering the terms:

$$ \mathcal{T}(n+1) = 2 \mathcal{T}(n) - \mathcal{T}(n/2) + \mathcal{T}((n+1)/2) + \Theta(1) $$

Since $(n+1)/2$ is either $n/2$ or $n/2+1$, it must be that $$ \mathcal{T}((n+1)/2) - \mathcal{T}(n/2) \ge 0$$

which means:

$$ \mathcal{T}(n+1) \ge 2 \mathcal{T}(n) + \Theta(1) $$

and:

$$ \mathcal{T}(n) \in \Omega(2^n) $$

We can check the other arrow (i.e. $ \mathcal{T}(n) \in \mathcal{O}(2^n) $) by induction.

# Answer
> 3 votes
To help with your intuition, change the code by substituting the code for bar into foo:

```
int foo(int x)
{
  if(x < 1) return 1;
  else if (x < 2) return 2; // foo(0) + bar(1), x = 1
  else return foo(x-1) + foo(x-1) + bar(x/2);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

```

So now it is obvious that T (x) ≥ $Θ(2^x)$, since foo (x) does two recursive calls to foo (x-1). Also makes it obvious that the result is foo (x) ≥ $Θ(2^x)$, and that result can be calculated in linear time.

---
Tags: complexity-theory, time-complexity, asymptotics
---


# Question
Title: Prove that if x has a predecessor, this predecessor has a right child
> In a BST, Let `x` be a leaf node, which is a left child of node `y`. Prove that if `x` has a predecessor, this predecessor has a right child.

How can I tackle this question? I'm not even sure from where to start.

# Answer
> 1 votes
In-order traversal (which is the case for a BST) starts at the leftmost leaf. This disqualifies the leftmost leaf from being the node in question since it would have no predecessor. All other leafs qualify. For all right leaves it follows that the predecessor has a right child (since the predecessor to any right leaf is it's parent). For all left leafs that are no the first leaf their predecessor is it's grandparent, which must have a right subtree for the leaf to exist. Ergo if a left leaf has a predecessor then this predecessor has a right subtree.

---
Tags: binary-search-trees
---


# Question
Title: Path in a graph with a given xor of weights of edges
I have an undirected weighted graph with $V$ vertices and $E$ edges. Weight of a path is a xor of weights of the edges on this path. Paths can pass through the same vertices and edges many times. Given two vertices $a$, $b$ and some number $x$ I want to tell if there exists a path of weight $x$. What is the fastest algorithm to solve this problem?

# Answer
## Arbitrary paths

If you want to know whether there exists a not-necessarily-simple path from $a$ to $b$ with weight $x$, here is a one-sided test:

Compute a cycle basis for the graph, $c\_1,\dots,c\_k$; this can be done in polynomial time. Let $p$ denote any simple path from $a$ to $b$. Let $W(p)$ denote its weight and $W(c\_i)$ the weight of the cycle $c\_i$. Then there exists a path of weight $x$ only if $x \oplus w$ is in the linear span of $W(c\_1),\dots,W(c\_k)$ (with all operations taken over $\mathbb{F}\_2$). This condition can be tested in polynomial time.

Why does this work? If there exists a path from $a$ to $b$, then it can be written as the xor (symmetric difference) of $p$ and some subset of $c\_1,\dots,c\_k$. Thus, its weight is given by $W(p)$ xored with the selected $W(c\_i)$ values.

However, the converse doesn't necessarily hold. If $x \oplus w$ is in the linear span of $W(c\_1),\dots,W(c\_k)$, there is no guarantee that there exists a path from $a$ to $b$. (The linear combination of $W(c\_1),\dots,W(c\_k)$ might correspond to a set of cycles that form a disconnected graph, and doesn't provide any way to form a path from $a$ to $b$.)

I don't know whether there is a polynomial-time algorithm or not.

## Simple paths

If you want to require the path to be a simple path, then the problem is NP-complete, by reduction from Hamiltonian path.

Let $G$ denote your graph. Suppose it has $n$ vertices, with vertices numbered from $1$ to $n$. Modify it to replace each vertex $v$ with two copies $v\_0$ and $v\_1$, and add an edge between $v\_0$ and $v\_1$. For each edge $(u,v)$ in the original graph $G$, we'll introduce edges $(u\_1,v\_0)$ and $(v\_1,u\_0)$ in the new graph, with weight zero ($0^n$). Each the edge $(v\_0,v\_1)$ will have a weight from $\mathbb{F}\_2^n$ that has the $v$th bit set and all other bits clear (i.e., its weight is $0^{v-1} 1 0^{n-v}$). Let $x$ denote a weight with all bits set (i.e., $1^n$).

Now there exists a simple path from $a\_0$ to $b\_1$ of weight $x$ in the new graph if and only if there exists a Hamiltonian path from $a$ to $b$ in the original graph. Therefore, any algorithm for your problem with paths restricted to simple paths immediately yields an algorithm for the Hamiltonian path problem, which is known to be NP-complete.
> 2 votes

---
Tags: algorithms, graphs, xor
---


# Question
Title: Is it possible to build short proofs of arbitrary folds over a huge list?
With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information close to just logarithm of the size of the whole tree. Merkle proofs, thus, probabilistically confirm the result of this specific fold:

```
isMember :: ∀ t . List t -> Bool
isMember e = foldr (\ h t -> h == e || t) False

```

My question is if the same result can be extended to arbitrary folds; or, in other words, is it possible to prove arbitrary computations over a big list using some clever trick similar to Merkle Trees?

### Formally

Given those 5 values:

1. `H :: String -> Uint256`, a fingerprint function
2. `H(X) :: Uint256`, the fingerprint of a dataset
3. `F :: String -> String`, an arbitrary computation
4. `Y :: String`, the claimed result of F(X)
5. A short proof

I need a `verify` function that returns `true` iff `F(X) == Y`, without having to run `F(X)`; perhaps not even having the whole original dataset `X`.

### Specific example

Suppose that you have a huge dataset (20 GB) distributed through a network of 100 computers that don't trust each-other. Is there any way for a computer to generate a claim such as `the sum of this dataset is 1650874919052809!`, so that other nodes are able to probabilistically verify that claim is correct, without actually running `sum dataset`?

# Answer
Yes, there is a generalization of the construction you mentioned. However, it's utility depends on the function `F`. The guarantees you get are meaningful only if `F` is robust, in the sense that you have to change a large fraction of the dataset to make any (meaningful) change to the output of the computation.

Suppose we have an untrusted agent Agatha who is going to do the computation for us and try to prove that she did it correctly. She'll build a Merkle tree in the same way, with one leaf per prefix of the list, and the leaf holding (the hash of) the intermediate state of the fold after processing that prefix. Thus, a list with $n$ items will involve construction of a Merkle tree with $n$ leaves. Agatha will send the hash at the root of the Merkle tree. She will also send the value at the rightmost leaf and a witness to its value. $\newcommand{\pl}{\operatorname{polylog}}$

Agatha will do $O(n)$ work to compute the fold and build the Merkle tree. We want the verifier to be able to verify the correctness of the result, using only $o(n)$ time and $o(n)$ communication with Agatha.

How will the verifier check Agatha's claimed result? The verifier can pick two adjacent leafs at random, ask Agatha to send a witness to the values at those two leaves, and re-apply `F` to check that the second was correctly obtained from the first. The verifier can repeat this many times. In each round, Agatha sends $O(\lg n)$ bits, and the verifier does $O(\lg n)$ work.

Now suppose Agatha cheats on at least a $p$ fraction of the `F` applications. Will this be detected? Well, each round has at least a $p$ chance of detecting Agatha's malfeasance. Thus, after $100/p$ rounds, there is a $(1-p)^{100/p} \approx e^{-100} \< 2^{-128}$ chance that Agatha's malfeasance goes undetected. In other words, $O(1/p)$ rounds suffice to detect Agatha if she cheats on at least a $p$ fraction of the applications of `F`.

On the other hand, if Agatha cheats on only a single application of `F` (say), she has a good chance of getting away with it; the verifier has no good way to detect this.

So, this construction is only useful if `F` is such that cheating on a small number of applications of `F` is harmless. This is closely related to the notion of a *robust* function, from robust statistics, which is about functions where changing a small number of inputs makes only a negligible change to the final output. For instance, since the sum, max, and min are not robust, this construction is not useful for computing the sum, max, and min. However, the median *is* robust, and the median can be computed securely via such a tree. As a simpler example, consider counting the number of entries in the database that match some pattern; this can be done securely via such a tree. In particular, Agatha can cheat on at most a $p$ fraction of nodes, and we can arrange that this changes the final count by at most $pn$. If that bound on the (additive, absolute) error is good enough, then we can achieve acceptable security.

In practice you probably typically don't want to use this kind of general construction. You can often do better by building a protocol that is specialized or customized for the particular function `F` you are dealing with. You can find many papers on this topic in the research literature, under names like "secure aggregation" or "outsourced computation" or "resilient aggregation". I've seen papers in the database literature, the cryptography literature, and the sensor network literature.

For example, if `F` is associative and commutative, and if the fold is robust, then we can obtain a secure Merkle tree scheme, where each internal node in the tree holds the result of the fold on a sublist corresponding to the subtree rooted at that internal node. (This is a bit different than the prefix construction mentioned earlier, and offers better security when `F` satisfies this property. The verifier needs to pick a random node and check that it was constructed correctly, rather than picking a random leaf.)

The preceding paragraph immediately lets you compute the "count" operator securely, up to an additive error of $\pm pn$. If we want to compute the median, Agatha can first compute the median offline, say $m$, then report $m$, and use a count query to count the number of data items that are $\le m$. The verifier can verify this count query up to an additive error of $\pm pn$, which proves that $m$ isn't "too far" from the true median (its rank differs from the rank of the true median by at most $\pm pn$, which in practice means it'll be quite close to the true median).

There's lots more one can say, and I've probably made oversimplifications at multiple points in this exposition, but hopefully this gives you some ideas and an entry point to the research literature on this subject.
> 5 votes

---
Tags: proof-techniques, cryptography, automated-theorem-proving
---


# Question
Title: Given the hash of a collection, H(X), can I build a proof that F(X) == Y, without having X?
Given a cryptographic fingerprint of a collection, `K == hash(X)`, an arbitrary function `F`, and a value `Y`, is it possible to build a short proof that `F(X) == Y` that doesn't require having `X`? I.e., a proof that `Y` is the result of applying `F` to some `X` such that `hash(X) == K`?

# Answer
> 5 votes
Yes, this is possible. Use a zero knowledge proof (of knowledge). If `F` is computable in polynomial time, then there exists a polynomial-time zero-knowledge proof of the property you want, i.e., given `K,Y`, the prover can construct a proof that there exists `X` such that `H(X)=K` and `F(X)=Y`. Amazingly, this proof is "zero-knowledge": it reveals nothing about `X` (other than the property is true).

If you don't care about the zero knowledge part, you can just use an interactive proof system.

Zero-knowledge proofs can be made non-interactive using standard techniques.

There's tons of work on this in the cryptographic research literature. I can't explain the ideas in the length of an answer here, so I suggest you spend some quality time studying this material. However, while the theory is elegant and beautiful, you're probably going to find the generic schemes are not very practical and the performance overhead is significant. Therefore, if you actually want to do this in practice, you'll want to focus on a specific function `F` and see whether you can build a custom protocol specialized to that particular function `F`.

# Answer
> 1 votes
The principle of a hash function is that multiple, different values can hash to the same key. The complexity of the hashing function determines how many possible values X may have. Consequentially it becomes impossible to prove that F(X) == Y if Y is a single value. After all, if X can be either 2 or 3 and F(X) = 2\*X then Y is both 4 and 6.

If F(X) is considered to be a set of possible solutions then you only have to prove that your given value 'Y' is a member of this set. The actual value of X is not a requirement to solve this problem and therefore it is possible to prove.

---
Tags: proof-techniques, cryptography
---


title: Minimum covering problem formulation

text:
# Question
Title: Minimum covering problem formulation
Shouldn't I post this question on mathematics.stackexchange.com?

> Let be an airlaine company which has to affect its aircrew to several flights. We group som flights in subset, every flights of a subset have to be realised by the same aircrew according to the actual possibilites and labour regulations. We provide a list, as rich a way as possible, of those combinations. Let be $E\_j$ the $j^{th}$ combination. We associate to $E\_j$ a cost $c\_j$ that take into account, for instance, the bonuses to aircrew for a time worked that would outreach th norms, etc...
>
> **The problem is to determine the combinations such that all flights are covered and that the cost is the minimal one.**
>
> **I have to give a formulation of this problem as a linear programing problem.**

The set of flights $V=\\{v\_1;...;v\_m\\}$

Let be $x\_j= \begin{cases} 1 \mbox{ if the combination $E\_j$ is taken}\\ 0 \mbox{ else} \end{cases}$

I don't understand the following formulation by my teacher. \begin{cases} \min &\sum\_{j=1}^{m}c\_jx\_j\\ &\sum\_{v\_i \in E\_j}x\_j&\ge 1\\ \end{cases}

But I quite understand the one given by Vangelis Paschos in Combinatorial Optimization:

> An instance of the MIN WEIGHTED VERTEX COVER. An instance of this problem (given the incident matrix $A$, of dimension $m\times n$, of a gaph $G(V,E)$ of order $n$ with $|E|=m$ and a vector $\bar w$, of dimension $n$ of the costs of the edges $V$), can be expressed in terms of linear program in integers as
>
> $$\begin{cases} \min &\bar w.\bar x\\ &A.\bar x &\ge \bar 1\\ &\bar x \in \\{0;1\\}^n \end{cases}$$
>
> such that $x\_i=1$ if the vertex $v\_i\in V$ is included in the solution $x\_i = 0$ if it is not included. The block of $m$ constraints $A.\bar x \ge \bar 1$ expresses the fact that for each edge at least one of these extremes must be included in the solution.

But I don't quite understand this notation $\bar 1$

> The feasible solutions are all the transversals of $G$ and the optimum solution is a transversal of $G$ of minimum total weight, that is a transversal corresponding to a feasible vector consisting of a maximum number of 1.

# Answer
Typically $\bar{1}$ represents the vector of 1s. In this case, $A\bar{x} \ge \bar{1}$ enforces the vertex cover constraint. The two formulations are the same, except the latter uses a more compact matrix notation to represent the inequality for each of the $j$ variables.
> 1 votes

---
Tags: graphs, linear-programming, set-cover
---