# Question
Title: Are coevolutionary "Free Lunches" really free lunches?
In their paper "Coevolutionary Free Lunches" David Wolpert and William Macready describe a set of exceptions to the No Free Lunch theorems they proved in an earlier paper. The exceptions involve two-player games in which a player tries to minimize expected search cost given optimal play, or at least good play, by an opponent.

Free lunches are "allowed" in this case because the exact choice of cost function to minimize changes depending on which fitness (i.e. objective) functions previous rounds of play have "ruled out." In other words, given that an opponent already knows something about the game, and chooses responses that minimize the player's expected return, the player can eliminate certain fitness functions without having to evaluate them. To illustrate how this works, W&M provide this chart:

Here, $\langle g \rangle$ represents the search algorithm that pays no attention to the opponent's moves; $\langle g \rangle\_{1}$ represents the search algorithm that considers all possible opponent replies to each move; and $\langle g \rangle\_{2}$ represents the search algorithm that samples just one possible opponent reply to each move.

This illustrates the character of the free lunch provided: algorithms that take into account information provided by the opponent do better than algorithms that don't, and those that collect as much information as possible from the opponent do better than those that only collect some. W&M amplify this point in their later discussion of opponent intelligence. They show that even when an opponent is not omniscient, but has partial knowledge, the player can exploit its partial knowledge. In the case of *total* ignorance this won't work because the opponent always replies with a random move. In that case, there appears to be no gain:

> the expected performance of the agent will be the average over the antagonist’s possible responses.

I guess this looks like $\langle g \rangle$ above. But in cases where the opponent has *some* knowledge, algorithm performance appears to increase monotonically with opponent intelligence.

What confuses me about all this is that the argument appears to boil down to the following trivial-seeming claim: across all problem domains, algorithms that bother to learn from knowledgable opponents do better than algorithms that do not. That is, as long as you don't *turn down* the free lunch, you can have it.

In effect, lunch is free because the opponent is buying.

If that's true, then couldn't we imagine a whole range of games in which, say, players play cooperative games with oracles, and those that refuse to cooperate perform worse on all problems? That's a free lunch in the same sense, right? But then we haven't explained where the oracle's knowledge comes from.

Does this mean that if we had to model the source of the other player's knowledge, we'd be back in the No Free Lunch zone? Or is the claim really that this sort of competitive play yields better outcomes even when both players start out in total ignorance, as the phrase "free lunch" seems to imply?

# Answer
Coevolutionary algorithms can't magically accelerate progress on any arbitrary problem class. So in that sense, the conclusion at the end of the question is correct. However, it doesn't follow that all coevolutionary free lunches are trivial, as the conclusion of the question suggests.

I can't offer an exhaustive account of all the kinds of coevolutionary free lunches, but I can offer two examples, the first of which is trivial, and the second of which I would argue is nontrivial. The second is nontrivial because it helps explain why the no free lunch theorem really must hold.

The important difference between the two examples is this: in the first, the competing algorithms are competing to achieve the same overarching goal, while in the second, the competing algorithms are trying to achieve different goals. In the second case, the mismatch between the two algorithms' goals allows interesting things to happen. I'll begin with the trivial example.

### Opponents seeking the same goal

Imagine a very simple optimization problem in which the search landscape is a 7x7 grid of cells. The primary goal is to find the cell with the maximum value. 48 of the cells have a value of 0, and one randomly chosen cell on the grid has a value of 1.

Our secondary goal is to discover a search strategy that finds the maximum value more quickly. But it follows from the initial problem that no strategy could possibly beat random search here, because nothing can be learned from one cell about another. Nonetheless, the coevolutionary free lunch theorem holds! Here's why:

Suppose you have two optimization algorithms, A and B, both searching the grid. It doesn't really matter what strategy they use, but for concreteness, we'll stipulate that they both use a random search strategy. The only difference between them is that B pays attention to A's moves, and when it sees that A has found the maximum value, it jumps to that cell too. In some sense, when that happens, B has still "lost" the contest. But if you run a lot of competitions, and then compare the average performance of A to the average performance of B, you'll see that B finds the maximum value faster on average.

The explanation is simple. The average time to first discovery -- whether by A or B -- stays the same. But whenever A beats B to the win, B doesn't bother looking anywhere else. It skips ahead to the best cell. When B beats A to the win, on the other hand, A just continues searching, plodding along until it finds the maximum value on its own.

This looks like a win if you're only counting the number of moves B makes. If you look at the total number of moves that A and B make together, they actually do worse together than either would on its own, on average. That's because of A's obliviousness. If we change A to behave the same way as B, then they do about as well together as either would on its own -- but no better.

So here, modeling both algorithms together returns us directly to the no free lunch zone, just as the question argues. In effect, A and B are just performing random search algorithms in parallel. The final number of search operations remains the same.

### Opponents seeking different goals

Now imagine a very different scenario. Suppose we have a classification problem: recognizing sheep. Here, A's job is to look at a stream of pictures and say whether there are sheep in them. Simple enough.

But B's job is very different. B has the power to inject pictures of its own into the stream! Its goal is not to identify sheep; it just wants to slow A down.

How can B do this? There's a great blog post and associated Twitter thread about a closely related question by Janelle Shane. The Twitter thread begins:

> Does anyone have a picture of sheep in a really unusual place? It's for pranking a neural net.

And here's one of the first replies:

> How about an orange sheep?

Here's the orange sheep:

Turns out, this was perfect for pranking:

> You totally got it. Orange sheep are not a thing it was expecting. "a brown cow laying on top of a lush green field"

Here are a couple of other examples from Shane's blog post:

So what does this have to do with our problem? We can connect them by being more precise. Suppose A's goal is to reach greater than 99% accuracy, and B has the power to inject one picture into A's stream for every nine "natural" pictures. B looks for patterns in A's behavior and uses them to find pictures that mess with its model. This will keep A's accuracy below 99% for much longer than if A saw only "natural" pictures.

Two things follow from this. First, B will do much better if it pays attention to what A does. If B just picks images on the basis of some randomly chosen general principle like "sheep in odd places," then there's a good chance that A will be prepared for them already. If not, it will quickly learn to handle them correctly, and B will then have to adopt a new strategy. On the other hand, if B watches A's behavior, it can pick out the specific things that A is worst at, and focus on those. As soon as A improves at one of them, B can have another one ready to go. As long as B can find patterns in A's behavior, B will always present the most challenging images for A.

Second, A will do much better if it pays attention to which images B picks. After all, B is looking for patterns in A's behavior. If it finds patterns, then it will use those patterns to send fake or troublesome pictures to A. In turn, that means that there will be noticeable patterns driving B's choices. Here again, if A is paying attention to the patterns in B's behavior, it will more quickly be able to identify which pictures B is injecting.

What's important is that in this scenario, both A and B are relying on data that is *guaranteed to have patterns*. It is guaranteed to have patterns because if A is doing its best, A is doing something other than random search. And if B is doing its best, then B is doing something other than random search.

So initially, this looks like a really compelling free lunch situation. But what have we actually shown? We've shown this:

> As long as A is doing something other than random search, B can always find out-of-band samples that A's methods cannot handle.

That's the no free lunch theorem in a nutshell!

The only way A can prevent B from finding out-of-band images is by behaving in ways that look random to B. But if A's behavior isn't *really* random, then in the very long run, B will always be able to find the pattern -- even if B itself is only doing random search.

The very same argument works in the other direction. The only way B can prevent A from noticing patterns in its images is by behaving in random-seeming ways. But if B's behavior isn't *really* random, A will eventually find the pattern, even if it's only doing random search.

In this scenario, both algorithms will try to fool each other by adopting more and more complex, random-seeming behaviors. So in the very, very long run, they will slowly converge to a truly random search -- which is the best any algorithm can do on average across all problem domains.

### An infinite pool of randomness

It might be that these coevolutionary learning strategies do still have this advantage over others: they may encourage both algorithms to explore the space of relevant non-random behaviors more quickly or extensively. I am not even sure of that. Either way, the no free lunch theorem holds in general, because the space of possible non-random behaviors is far, far smaller than the space of possible random behaviors.

How do we know? It would be off topic to go into a detailed proof, but consider the related question of how many long strings can be compressed into shorter strings. Regardless of the compression method, the majority of all strings cannot be compressed at all. This is easy to prove with a bin-counting argument. Suppose we consider binary strings, and start with the empty string. Assuming there can be no negative-length strings, that's incompressible. Now consider length-1 strings. There are two, but there's only one length-0 string, so only one of them can be compressed. Now we have two incompressible strings, and a third string that can be compressed by one bit. Moving on to length-2 strings: there are four, but there are only two length-1 strings, and the one length-0 string is already taken, so we can only compress two of the length-2 strings. The other two are incompressible. That's three compressible strings and four incompressible strings... and so on.

As the numbers get higher, one of the things you notice is that even among the compressible strings, half of them are only compressible by one bit, because they compress to strings that are themselves incompressible. A quarter are only compressible by two bits; an eighth are only compressible by three bits. No matter how you slice it, the number of substantially compressible strings is always much lower than the number of strings that are incompressible or barely compressible.

The line of reasoning for random behavior is similar. You could also connect these ideas to the proof that there are vastly more real numbers than integers. In the global scheme of things, the no free lunch theorem is true because the scope of randomness is unimaginably vast.
> 2 votes

---
Tags: optimization, machine-learning
---


# Question
Title: Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?
I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, optimally combining the score means minimizing, but that's probably not important

Formally stated:

1. We have the function SCORE(L) that computes score for a list.
2. Each adjacent pair of list elements L\[i\],L\[i+1\] can be replaced by element produced by the function COMBINE(L\[i\],L\[i+1\]). This operation can be repeated recursively, further shortening the list.
3. COMBINE is associative and commutative, i.e. COMBINE(A, COMBINE(B, C)) == COMBINE(COMBINE(A, B), C) and COMBINE(A, B) == COMBINE(B, A)
4. Given list L and functions SCORE/COMBINE, we need to find best score that can be reached on L or any its reduction.

So, as an example, if I have the list \[A, B, C, D\], all of these options are to be considered: (AB denotes the combination of A and B):

```
[A, B, C, D], [A, B, CD], [A, BCD], [A, BC, D], [AB, C, D], [AB, CD], [ABC, D], [ABCD]

```

Two obvious options include brute force (thanks, no) and a greedy algorithm, which would go roughly as follows in ~~pseudocode~~ Python:

```
def greedily_combine( elements, combine, score ):
    i = 0
    combine_success = False
    while i < len( elements ) - 1:
        combine_candidate = [combine( elements[i], elements[i+1] )]
        sublist_to_consider = elements[0:i+1]
        combined_score = score( combine_candidate )
        uncombined_score = score ( sublist_to_consider )

        if ( combined_score < uncombined_score ):
            elements.pop(0)
            elements.pop(0)
            elements.insert(0, combine_candidate)
            combine_success = True
        else:
            i += 1
            if i == len( elements ) - 1:
                i = 0
                combine_success = False

    return elements

```

However, this is almost certainly not going to be optimal. Is there a known general solution? If not, how could I have seen this myself, and is my greedy search good or easily improvable?

# Answer
In your formulation, you need to compute score of each reduced list individually. So, if there are 2^(n-1) possible reduced lists, you need to perform at least O(2^n) operations.

Unless you can figure out some restrictions or relations between scores of related lists (such as "longer lists always have better scores"), it will remain O(2^n) problem.
> 3 votes

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


# Question
Title: 1D Peak-finding problem, how to derive the formula?
I couldn't find a good answer to how this formula was derived for the divide and conquer algorithm in a 1D Peak-Finding problem.

### **About the problem**

Basically, there's an array of numbers and we want to find *a* peak in this array (a peak is a number higher than the two numbers to the left and right of it).

### The formula

> $T(n) = T(n/2) + \Theta(1)$

I watched the MIT video on "1. Algorithmic Thinking, Peak Finding" but the formula was just written as though it was something really obvious. I guess it might be, anyone kind enough to explain it?

I can sort of guess that $n/2$ comes from the fact that we are always choosing only one side of the array, but this is really just a guess and I get totally lost when suddenly the formula is expanded and we get

> $\Theta(\log\_2 n)$

instead...

# Answer
> 2 votes
Your guess is absolutely correct. The time taken to process an array of length $n$ is the time taken to choose which half to recurse on, plus the time taken to do the recursion. Doing the recursion takes time $T(n/2)$, since $T(m)$ is, by definition, the time taken to process an array of length $m$. Choosing which half to recurse on takes some constant number of steps, which is what $\Theta(1)$ means. So this gives us that $T(n) = T(n/2) + \Theta(1)$. And, implicitly, $T(1)=\Theta(1)$ since, if the array has length one, there's no recursion to do.

How to solve that recurrence to get $T(n)=\Theta(\log n)$ is covered by our reference question. A rough-and-ready way to see it is to observe that the length of the array halves on each recursive call, so the number of recursions before we reach a single-element array is the answer to the question "How many times can I divide $n$ by two before I get $1$?", which is $\log\_2 n$.

# Answer
> 0 votes
I had the same issue when I was watching the first video recently.

I don't know what your background is, but if you already have some basic grounding in discrete mathematics, I suggest you take the formal way to understand it.

That is, take any good basic discrete mathematics textbook and read the section on recurrence relations and algorithm complexity. Personally, I referred to Susanna Epp's Discrete maths textbook (section 5.7, 11.2, 11.3, 11.4, 11.5). Depending on your background, you may need to read more or less sections. It helped me immensely understand lectures on recursive algorithms.

Since "MIT 6.006 Introduction to Algorithms" seems that it's mostly about learning to measure time complexity of various algorithms, I strongly recommend that you grab a discrete maths text and gather mathematical foundations as you go.

I'm currently doing this, and the next sections I need to read from Epp's text are regarding trees, graphs, and discrete probability.

I honestly think that you cannot get much out of 6.006 if you don't study basic discrete mathematics. You will not be able to understand time complexity.

---
Tags: algorithms, algorithm-analysis, arrays
---


# Question
Title: Bottleneck in Hoare Logic unable to arrive at my {P} from {Q}
{Q} = {n\>0}
C1 = i := 1;
C2 = c := 1;
C3 = p := 0;
{P} = {i\<=n, p = fib(i-1), c = fib(i)}

My lack of understanding towards the rule of consequence in hoare logic is blocking me from find the solution which i hope someone can shed some light on how can i approach this with minimal abstraction of the process.

{R} = {i\<=n,p=fib(i-1),c=fib(i)\[i\1\]} i:= 1;{i\<=n, p = fib(i-1), c = fib(i)}

{R} = {1\<=n,p=fib(0),c=fib(1)}

{R} = {1\<=n,p=0,c=1}

{R1} = {1\<=n,p=0,c=1\[c\1\]}c:=1;{1\<=n,p=0,c=1}

{R1} = {1\<=n, p=0, true }

{R2} = {1\<=n,p=0\[p\0\]}p:=0;{1\<=n,p=0}

{R2} = {1\<=n, true}{1\<=n,p=0}

{R2} = {1\<=n -\> 0\>x} :( i can't arrive at exactly n\>0

\*edit

From my observation the key problem is regardless of sequence i would always arrive at 1\<= n as not equivalent to n\>0, i am not sure how i can legally perform P-\>P’ P’ C Q’ Q’-\>Q to prove {P}C{Q}

# Answer
You are doing it in the opposite order. You are starting with the postcondition `{i<=n, p = fib(i-1), c = fib(i)}` and then computing the precondition relative to the *first* assignment. You should instead use the *last* assignment, and go backwards:

```
{Q} = {n>0}
{P3 = P2[i\1]} = {1<=n, 0 = fib(1-1), 1 = fib(1)}
C1 = i := 1;
{P2 = P1[c\1]} = {i<=n, 0 = fib(i-1), 1 = fib(i)}
C2 = c := 1;
{P1 = P[p\0]} = {i<=n, 0 = fib(i-1), c = fib(i)}
C3 = p := 0;
{P} = {i<=n, p = fib(i-1), c = fib(i)}

```

The steps above were computed bottom-up: you should read it in the same way.

It is then simple to check that `Q` and `P3` are equivalent (assuming integer variables).
> 1 votes

---
Tags: hoare-logic
---


# Question
Title: Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix
Consider a $n \times n$ matrix $A$ with $k$ nonzero entries. Assume every row and every column of $A$ has at most $\sqrt{k}$ nonzeros. Permute uniformly at random the rows and the columns of $A$. Divide $A$ in $k$ submatrices of size $n/\sqrt{k} \times n/\sqrt{k}$ (i.e. $\sqrt{k}$ meta-rows and meta-columns). Enumerate the $k$ nonzeros and define the following indicator random variable:

\begin{equation} X\_{\ell,z} = \begin{cases} 1 & \text{if the $z$-th nonzero entry is in $A^\ell$} \\ 0 & \text{otherwise} \end{cases} \end{equation}

The expected number of nonzero entries in a generic submatrix $A^\ell$ is one. Is it possible to prove Chernoff-Hoeffding bounds on the sum $X\_\ell = \sum\_{z=1}^k X\_{\ell,z}$?

My first guess was to prove negative association, following Dubhashi and Panconesi analysis. Unfortunately, $X\_{\ell,z}$ and $X\_{\ell,z^\prime}$ are not negatively associated (following the book's notation, if $z$ and $z^\prime$ are in the same row/column then $\mathbf{E}\[f(X\_{\ell,z})g(X\_{\ell,z^\prime})\] \> \mathbf{E}\[f(X\_{\ell,z})\] \mathbf{E}\[g(X\_{\ell,z^\prime})\]$).

# Answer
> 3 votes
Okay, here is a full answer.

We will use the fact, that any bipartite graph of maximum degree $d$ can be broken into (at most) $d$ matchings.

In our case, this means that we can split $A$ into (at most) $\sqrt{k}$ disjoint sets of elements $S\_i\subseteq\\{(i,j)\in\[n\]\times\[n\] \mid A\_{i,j}=1\\}$ of size at most $n$ such that any every element in each set has a unique row and column. (This uses that a $1$ in $A$ can be seen as an edge in the $n\times n$ bipartite graph that is the matrix.)

Now let $X$ be the total number of $1$s in your $n/\sqrt k\times n/\sqrt k$ matrix, $A^\ell$, and let $X\_i$ be the number of elements coming from $S\_i$. Then $X\ge t\implies \exists\_i\\, X\_i\ge t/\sqrt k$ and so $$\Pr\[X\ge t\]\le \sqrt k \Pr\[X\_1 \ge t/\sqrt k\]$$ by the union bound. Now, because elements in $S\_1$ don't share any rows/columns, it is easy to analyze using your original approach.

In particular, reorder the rows and columns using the matching, so that the first element in $S\_1$ is $(1,1)$ the next is $(2,2)$ and so on. Let $r\_i$ be the random variable that is 1 if row $i$ is chosen and $c\_i$ likewise. Then we want to upper bound $\Pr\[\sum\_i r\_ic\_i \ge t\]$. Notice $E\[r\_ic\_ir\_jc\_j\] = E\[r\_ir\_j\]E\[c\_ic\_j\] \le E\[r\_i\]^2E\[c\_i\]^2$ by Maclaurin’s Inequality, so $$\exp(t\sum\_i r\_ic\_i) = \sum\_k t^k/k!\\,E\left(\sum\_i r\_ic\_i\right)^k \le \sum\_k t^k/k!\\,E\left(\sum\_i b\_i\right)^k = \exp(t\sum\_i b\_i)$$ where $b\_i$ is a normal binomial variable with $p=(n/\sqrt{k}/n)^2=1/k$.

Finally, we then get

$$\Pr\[X\ge t\]\le \sqrt k \Pr\[X\_1 \ge t/\sqrt k\] \le \sqrt k \exp\left(-2\left(\frac{t-p n \sqrt{k}}{n\sqrt k}\right)^2 n\right)$$

or more simply

$$\Pr\[X\ge \lambda\sqrt{nk}+n/\sqrt k\]\le \sqrt k \exp(-2\lambda^2)$$

or if we use the Hoeffding bound for small values of $p$ (large $k$):

$$\Pr\[X\ge \lambda\sqrt{nk}+n/\sqrt k\]\le \sqrt k \exp\left(\frac{-\lambda^2}{2/k+\lambda/\sqrt n}\right)$$

Note that if we had simply assumed all elements were independent, we would have gotten the bound $\Pr\[X\ge \lambda\sqrt{n\sqrt{k}}+n/\sqrt k\]\le \exp(-2\lambda^2)$. Equal to ours except for a factor $k^{1/4}$ in the exponent.

---
Tags: permutations, sparse-matrices, chernoff-bounds
---


# Question
Title: Are there any known AM-complete problems/is AM-complete well defined?
I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem **in** AM, but it's probably not a complete one.

I suppose I'm also wondering if a "complete" problem is well-defined for AM. Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes. So maybe since Karp reductions have no error, "Karp reducing to an AM problem" doesn't really have any meaning, thus invalidating the usual notion we use of a "complete" problem?

# Answer
> 1 votes
> Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes.

This is a wrong intuition. Regardless of how you define your complexity class $\mathbb{C}$, if there exists any problem $\mathrm{A}\in \mathbb{C}$ such that for every problem $\mathrm{B}\in \mathbb{C}$, you have $\mathrm{B} \leq\_p \mathrm{A}$, then $\mathrm{A}$ is a many-one complete problem of $\mathbb{C}$.

In fact, even a problem that is complete by randomized reductions for $\mathrm{AM}$ is not known. Put in other word, it seems very hard to just pin down any particular decision problem in $\mathrm{AM}$ so that we can have some *non-trivial reduction* from other problems known to be in $\mathrm{AM}$.

> See mathoverflow.net/questions/34469 and cstheory.stackexchange.com/questions/1233; in short, the definition of AM relies on a promise, and this makes it tricky to define a reduction. – sdcvvc

That is one of the obstacles on the way to find a complete problem for $\mathrm{AM}$. This is also applicable to $\mathrm{BPP}$, $\mathrm{RP}$, $\mathrm{co}$-$\mathrm{RP}$, $\mathrm{ZPP}$. These classes requires the poly-time probabilistic Turing machine to have bounded error probability on all instances. The situation is much easier for $\mathrm{PP}$, this class does not put any requirement on the error probability, whichever result has the higher probability is the answer of the machine so we can easily catch a complete problem for it, namely $\mathrm{MAJ}$-$\mathrm{SAT}$.

---
Tags: complexity-theory, reductions, complexity-classes, interactive-proof-systems
---


# Question
Title: Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $
I was reading the following paper by Jim Kadin, "$P^{NP\[O(\text{log } n)\]}$ and sparse Turing complete sets for NP"

The main result is that if there is a sparse set $S \in NP$ such that $coNP \subseteq NP^S $, then $PH \subseteq P^{SAT\[O(\text{log }n)\]} $.

In the proof of this result he author claims that it is sufficient to prove $NP^ {SAT} \subseteq P^{SAT\[O(\text{log }n)\]}$ and this will imply that $PH \subseteq P^{SAT\[O(\text{log }n)\]} $.

I could not figure out why this is true. Perhaps this is trivial and there is some minor point (some inclusion of complexity classes) that I am missing. Please do point out why the above claim is true.

# Answer
> 1 votes
Simply put, even a weaker claim of $\mathrm{NP}^\mathrm{SAT}=\mathrm{NP}^\mathrm{NP}\subseteq \mathrm{P}^\mathrm{SAT}=\mathrm{P}^\mathrm{NP}$ would imply PH collapse to the second level (so even the consequence is a little bit weaker, you can adapt to your case).

We have $\mathrm{P}^\mathrm{NP}\subseteq \mathrm{co}$-$\mathrm{NP}^\mathrm{NP}$. So, from the assumption, we deduce that $\mathrm{NP}^\mathrm{NP}\subseteq \mathrm{co}$-$\mathrm{NP}^\mathrm{NP}$. As a result, PH collapse to the second level.

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


# Question
Title: Are there any decision complexity classes which have no "complete" subclass?
Are there any decision complexity classes, where the "-Hard" version of the class does not intersect with the original class?

# Answer
> 3 votes
Apart from the many answers from the Mathoverflow link commented above by Ariel, we have a very simple example as follows.

Under widely accepted conjecture that $\mathrm{P}\neq \mathrm{NP}$, we have that $\mathrm{NP}\setminus \mathrm{NP}$-$\mathrm{complete}$ does not have complete problem and therefore the "hard" part of it is well "above" it.

For the proof, use Ladner's result on $\mathrm{p}$-degree, for any two different $\mathrm{p}$-degrees $\mathrm{A}$ and $\mathrm{B}$, if $\mathrm{A}\<\_p\mathrm{B}$, then there must exist another $\mathrm{p}$-degree $\mathrm{C}$ in between: $\mathrm{A}\<\_p\mathrm{C}\<\_p\mathrm{B}$. So by removing $\mathrm{NP}$-$\mathrm{complete}$ from $\mathrm{NP}$, every $\mathrm{p}$-degree below the complete degree always has another non-complete degree above it.

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


# Question
Title: Representing a network with two types of connections: A fishing application
I want to represent a fishing network using a graph representation. My question surrounds how I can write the adjacency matrix if there are two types of connections, which I want to capture together.

Here's the most basic setup. Say there are two people represented by nodes.

1. Person one owns a fishing right and also acts as an authority who can land fish.
2. Person two is a fisherman.

Person one sells the signle fishing right to person two. Person two catches the fish and sells the fish back to person one. Intuitively, I want to write a directed adjacency matrix, in which positive *i,j* values represent the fishing rights transaction and negative *j,i* values represent the physical fish transaction, which leads to the following adjacency matrix:

\begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}

**My question is:** Can I use signs like this to represent related but distinct connections? The basic logis follows from the fact the total fish caught = the total fishing rights. By summing the elements, we get zero representing a closed system. Here is a more complicated example:

\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & -1 & 0 \\ \end{bmatrix}

In this example person one sells the fishing right to person two as before. Now there is a person three, however, who lands the fish. Again the sum of all the elements is zero as total fishing rights = total fish caught. The network captures a different reality, however. In this second network, all the activities are separated as in an open market. In the original network, all the activities were through a relationship between person one and person two.

# Answer
> 2 votes
Sure, of course. You can define a matrix to contain whatever numbers you want it to contain. There's nothing that prevents you. The real question is whether the result has the properties you want it to have, but since you haven't listed any properties, there's nothing to answer here.

# Answer
> 1 votes
Assuming for the moment that the two types of person are distinct, your graph is (directed) bipartite, so it makes more sense to store it as a matrix whose rows correspond to people with fishing rights, and whose columns correspond to fishermen.

If a person can function in both roles, you can think of their two personas as distinct, i.e., have a row and a column for each.

---
Tags: graphs, weighted-graphs, social-networks, network-analysis
---


# Question
Title: Get count of longest zigzag sub-sequences
I know how to get longest zigzag sub-sequence and length of it. There are several methods available for that. But some times there are many sub-sequences available which have same length. How to obtain that?

# Answer
> 1 votes
Extending the well-known dynamic programming algorithm for Longest Common Subsesequence, we have a poly-time algorithm for Longest Zig-zag Subsequence.

When DPing, just also add another parameter: $\mathrm{A}\[\mathrm{i}\]\[\mathrm{j}\]$ is the length of the longest zig-zag sequence ending at position $i$ and it is increasing when it ends at $i$ if $j = 0$ and otherwise, decreasing when it ends at $i$ if $j = 1$. So, at a position $i$, you scan from $1$ to $i-1$ and update $\mathrm{A}\[\mathrm{i}\]\[\mathrm{0}\]$ and $\mathrm{A}\[\mathrm{i}\]\[\mathrm{1}\]$ gradually. Note that you need to make the $\mathrm{j}$-index alternate while updating.

---
Tags: dynamic-programming, longest-common-substring
---


# Question
Title: How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?
How to prove that a string, `s` is made up of `n > 1` subsequences occurring some arbitrary number of times using concatenation and stripping first and last character? E.g `s = xyzxyz`, subsequence is `xyz` and it occurs 2 times. The solution is to concatenate the same string e.g. `xyzxyzxyzxyz` and then strip the first and last character to get `yzxyzxyzxy`, then you find `s` (`xyzxyz`) inside that.

Other examples:

1. The word `Table` does not have a subsequence so the above method will give: `Table||Table` -\> `TableTable` -\> `ableTabl` -\> which does not contain Table so Table does not contain a subsequence
2. The word `mmebmmebmmeb` -\> has to return true with the above method because it contains `mmeb` repeated 3 times. So, `mmebmmebmmeb || mmebmmebmmeb` -\> `mmebmmebmmebmmebmmebmmeb` -\> (strip first and last) `mebmmebmmebmmebmmebmme` which contains `mmebmmebmmeb` (`meb**mmebmmebmmeb**mmebmme`)

My thought was to assume that there is at least one character in `s` that will invalidate the occurrence of a subsequence. E.g. instead of `xyzxyzxyz` (`xyz` occurring three times) we have `xyzxyzxya` where `a` is the wrong char. Now we assume that in `yzxyzxyaxyzxyzxy` (after concatenation and stripping first and last) that the string `s` does exist which should be a contradiction - but I am stuck.

Could someone give me a formal mathematical proof?

Looked at this for ideas: How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?

# Answer
Let us first state the theorem that we are trying to prove.

**Theorem.** Let $w \neq \epsilon$ be a word. Then $w^2 = xwy$ for $x,y \neq \epsilon$ if and only if $w = z^p$ for some $p \> 1$.

**Proof.** Let us first suppose that $w = z^p$ for some $p \> 1$. Then $w^2 = z^{2p} = zwz^{p-1}$, where $z,z^{p-1} \neq \epsilon$.

In the other direction, write $w = w\_1w\_2$, where $|xw\_1| = |w\_2y| = |w|$. Since $x,y \neq \epsilon$, we see that $|w\_1|,|w\_2| \< |w|$. We have $ww = xw\_1w\_2y$ implies that $w = xw\_1 = w\_2y$, and so $x = w\_2$ (since $|x| = |w|-|w\_1| = |w\_2|$). In other words, $w = w\_2w\_1$.

Now let $w = \sigma\_0 \ldots \sigma\_{n-1}$, and let $|w\_2| = m$. Note that since $|w\_1|,|w\_2| \< n$, we have $0 \< m \< n$. The equality $w = w\_2w\_1$ implies (check!) that $\sigma\_i = \sigma\_{i+m \bmod{n}}$. Let $g$ be the GCD of $m$ and $n$; note that $g \< n$. It is known that $g = am + bn$ for some integers $a,b$, and so $\sigma\_i = \sigma\_{i+bm \bmod{n}} = \sigma\_{i+g \bmod{n}}$. Since $g \mid n$, this implies that $w = (\sigma\_1 \ldots \sigma\_g)^{n/g}$, where $n/g \> 1$.
> 0 votes

---
Tags: formal-languages, proof-techniques, induction
---


# Question
Title: Why is the sequence, "1,3,2,4", not a bitonic sequence?
A **Bitonic Sequence** is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.

According to the definition of a bitonic sequence, we know that a graph of a bitonic sequence can have at most one "peak" and one "valley".

So, why is the sequence `1,3,2,4` not a bitonic sequence?

I have referred the book, "Parallel Computing", by M. J. Quinn.

# Answer
In this sequence, lets consider 3 as the bitonic point. So 1,3 makes for a strictly increasing series.

However after we cross the bitonic point 3, 2 and 4 do not make a strictly decreasing series.

Another point in Bitonic Series' is that we have to take into account circular bitonic patterns. So a series like `1 2 5 0 -5 -2` is bitonic since we monotonically increase from `1 to 5`, then monotonically decrease from `5 to -5` and again we monotonically increase from `-2 to 5`.

In the case of `1 *3* 2 *4* 1`, there are 2 peaks occurring and hence its not even circularly bitonic.
> 2 votes

# Answer
According to your definition, a sequence $x\_1,\ldots,x\_n$ is bitonic if there exists an index $i$ such that $x\_1 \< x\_2 \< \cdots \< x\_i$ and $x\_i \> x\_{i+1} \> \cdots \> x\_n$.

In your case, this means that one of the following must holds: $$ 1 \> 3 \> 2 \> 4 \\ 1 \< 3 \> 2 \> 4 \\ 1 \< 3 \< 2 \> 4 \\ 1 \< 3 \< 2 \< 4 $$ You can check that none of these options works.

Another way to see this is to notice that your sequence has an ebb, $x\_3 = 2$, which cannot happen in a bitonic sequence.

A third way is to notice that a sequence is bitonic if the $\<,\>$ pattern is of the form $\<^\*\>^\*$ (in regular expression parlance). In your case, $1 \< 3 \> 2 \< 4$, and so the pattern is $\<\>\<$, which is not of this form.
> 2 votes

---
Tags: parallel-computing
---


title: Aho-Corasick for a set of patterns

text:
# Question
Title: Aho-Corasick for a set of patterns
I have completely understood how Aho Corasick works for finding one pattern in a text, and how to construct the automaton for a certain pattern. I have studied the CLRS book and watched this video. But the problem is that I cannot find any material on how to build an automaton for more than just one pattern. For example given the following words, how can I build an automaton with the required transition function?

P = {vine, vincent, cent, center}

Are there any topics on StackOverflow or any YouTube videos that teach this step-by-step?

# Answer
> 9 votes
At a high level, the process for building an Aho-Corasick automaton is:

1. Build a trie for the pattern strings.
2. Add suffix links (also called failure links) from each node to its longest proper suffix that's still in the trie.
3. Add output links to any patterns that are reachable from each node via suffix links.

## Build the trie

Create a root node, then go through each pattern character by character. Starting from the root, try and follow an edge for the current character. If one does not exist, create an edge to a new node for that character.

Using P = {vine, vincent, cent, center}, say we start with the pattern 'vine'. When we go and add the next pattern 'vincent', we first follow the existing edges for v-i-n, and then add in new edges for c-e-n-t:

(I'm marking the ends of each pattern with a double circle). Continue this process until the whole trie is built:

## Add suffix links

Now to add the suffix links, we perform a breadth first search of the tree, adding an edge for each node except the root. If a node is one hop away from the root, its suffix link goes to the root. Adding suffix links in blue, the suffix links for the nodes corresponding to 'v' and 'c' are:

Otherwise, the node corresponds to some string *wx*, where *x* is the final character. For example, if we look at the string 'vi', *w*='v' and *x*='i'. Now follow *w*'s suffix link and let the node you arrive at be called *n*.

If this node has an edge for *x*, then set *wx*'s suffix link to point at *nx*. Else if *n* is the root node, set *wx*'s suffix link to point at *n*. Otherwise, follow *n*'s suffix link, let this node be the new *n*, and repeat. In this case, the node for *n* does not have an edge for 'i'. Here's another example adding in the suffix link for 'vinc', where *w*='vin' and *x*='c':

## Add output links

As you are performing the BFS to fill in the suffix links, you can also fill in the output links (all initially null). Let the current node be *n*. Follow *n*'s suffix link and let the node you arrive at be called *m*.

If *m* corresponds to one of the pattern strings (is marked with a double circle), set *n*'s output link to point at *m*. Else set *n*'s output link to point at the same node as *m*'s output link, or null if *m* has no output link. In our example there is only one output link, shown here in green:

---
Tags: algorithms, finite-automata
---


title: Invertability of Karp reductions

text:
# Question
Title: Invertability of Karp reductions
Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$.

I am interested in polynomial-time invertability of Karp reductions between *natural* NP-complete problems.

> Is it true that every Karp reduction $f$ is also polynomial-time invertible (i.e. $f^{-1}$ is polynomial-time computable)?

To clarify, Is there a Karp reduction $f$ between two *natural* NP-complete problems where its inverse $f^{-1}$ is not known to be polynomial-time computable?

Natural problem means that the problem is not an artificially made up problem to answer the question (or similar ones) and people are interested in the problem independently (defined by Kaveh).

P.S. It is known that all known Karp reductions between *natural* NP-complete problems are injective (or can easily made injective).

# Answer
> 0 votes
1. **YES** if $\mathrm{P}\neq \mathrm{NP}$ and **the $3$-$\mathrm{SAT}$ problem satisfies your requirement (when being reduced to other complete ones)**. In short, this is the *equivalent* statement of *your conjecture*.

Unconditionally, every $\mathrm{NP}$ problem not necessarily complete can be reduced to $3$-$\mathrm{SAT}$ by a reduction $f$ which is poly-time invertible. And composition $f \circ g$ of efficiently invertible $f$ and $g$ is also efficiently invertible. Therefore, if somehow we prove that $3$-$\mathrm{SAT}$ problem satisfies your requirement (when being reduced to other complete ones), then your conjecture holds.

When reducing to $3$-$\mathrm{SAT}$, simply append dummy clauses to the $3$-$\mathrm{SAT}$ instance. These dummy clauses just encodes the original instance. And of course, these are trivially satisfiable with brand-new dummy variables.

For example: suppose $x=x\_1x\_2\dots x\_n$ is the original instance and your $3$-$\mathrm{SAT}$ instance already has $k$ variables, do the following:

for each original bit $x\_i$:

* if $x\_i=0$, add dummy clause $x\_{k+1}\lor \lnot x\_{k+1}$ if $k+1$ is even, otherwise add dummy clause $x\_{k+2}\lor \lnot x\_{k+2}$
* if $x\_i=1$, add dummy clause $x\_{k+1}\lor \lnot x\_{k+1}$ if $k+1$ is odd, otherwise add dummy clause $x\_{k+2}\lor \lnot x\_{k+2}$
* $k$ := $k + 1$

2. **NO** if $\mathrm{P} = \mathrm{NP}$. This is because if so, a sparse language can be $\mathrm{NP}$-complete rendering hopeless a poly-time injective reduction (from a non-spare language to it).
    3. Your conjecture is impied by the much stronger isomorphism conjecture. That is why many attempts to partially resolve that conjecture (e.g. by deduce it from weaker statements like yours) all fail up to now.

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


# Question
Title: Is boolean formula isomorphism NP-complete?
*Problem*. Given 2 functions $f,~g$ of the same length $n$, decide if we can change variables in $f$ such that it will be identical to $g$. There are exponentially many non-isomorphical functions (as number of total assignments is bounded by exponent).

*Example*. $f=(x\land y\land z)\lor(\overline x\lor z)$. $g=(x\lor\overline y)\land(x\lor y\lor z)$.

Replacing $x$ and $y$ in $g$: $g = (\overline x\lor y)\land(x\lor y\lor z)$.

Replacing $y$ and $z$ in $g$: $g = (\overline x\lor z)\land(x\lor y\lor z)$. It became equal to $f$.

While this is considered not to be $\mathsf{NP}$-complete for 2SAT (we can compare their implication graphs and this is GI), is this problem $\mathsf{NP}$-complete for other variants of SAT (Horn3SAT, XOR3SAT, unambiguos 3SAT; if not, then at least 3SAT)?

Also there are two variations of problem:

1. All clauses in formula become equal (but in this case number of non-isomorphic functions is superexponential).
2. Number of satisfying assignments is equal (don't suspect to be in $\mathsf{NP}$ except for 2SAT; and it is $\mathsf{NP}$-hard for 3SAT).

# Answer
Your problem is $\mathrm{co}$-$\mathrm{NP}$-hard so it may also be $\mathrm{NP}$-hard but very unlikely to be $\mathrm{NP}$-complete (i.e. to be in $\mathrm{NP}$).

We reduce from **TAUT** which is $\mathrm{co}$-$\mathrm{NP}$-hard. Given a **TAUT** instance $\varphi$ with variables $x\_1,\dots x\_n$, output $\<\varphi, ((x\_1 \lor \lnot x\_1)\land\dots\land (x\_n \lor \lnot x\_n))\>$. These two formulae are isomorphism iff. $\varphi$ is a tautology.
> 2 votes

---
Tags: np-complete, boolean-algebra
---


# Question
Title: Is $A\odot B\odot C = A\oplus B\oplus C$?
(The notations used:

I was solving a problem, where they asked which of the given options give equation for the difference of full subtractor. The circuit in the solution option was:

For me the first line:

> $(x'y'+xy)'z'+(x'y'+xy)z$

looked more like $x\odot y\odot z$. But I know the difference of full subtractor is $x\oplus y\oplus z$. So I tried to evaluate both separately:

> $x\oplus y\oplus z$
> $= (x'y+xy')\oplus z$
> $= (x'y+xy')'z+(x'y+xy')z'$
> $= (x'y)'(xy)'z+(x'y+xy')z'$
> $= (x+y')(x'+y)z+(x'y+xy')z'$
> $\require{enclose}= \enclose{updiagonalstrike}{xx'z}+xyz+x'y'z+\enclose{updiagonalstrike}{yy'z}+x'yz'+xyz'$
> $= xyz+x'y'z+x'yz'+xy'z'$ ...equation$(I)$
>
> $x\odot y\odot z$
> $=(x'y'+xy)\odot z$
> $=(x'y'+xy)'z'+(x'y'+xy)z$ (This is same as first line in the equations given in the figure above)
> $=(x'y')'(xy)'z'+(x'y'+xy)z$
> $=(x+y)(x'+y')z'+(x'y'+xy)z$
> $\require{enclose}=\enclose{updiagonalstrike}{xx'z}+xy'z'+x'yz'+\enclose{updiagonalstrike}{yy'z'}+x'y'z+xyz$
> $=xy'z'+x'yz'+x'y'z+xyz$ ...equation$(II)$

To my eyes, both equations $(I)$ and $(II)$ looks the same. So I went to wolframalpha and prepared truth table for both of them.

$x\oplus y\oplus z$

$x\odot y\odot z$

And they correctly look complement of each other. Then why the given answer and my calculations equates $x\odot y\odot z$ with $x\oplus y\oplus z$? What stupidity I am doing here?

# Answer
Yes, $x\odot y\odot x = x\oplus y\oplus z$, where $\oplus$ is the XOR operator and $\odot$ is the XNOR operator.

In fact, it is easy to see that both sides of the equation are always equal. Note that $a\odot b$ tests whether $a$ is the same as $b$ while $a\oplus b$ tests whether $a$ is different from $b$. So we know $a\odot b= \overline{a\oplus b} = \overline a\oplus b$. So, $x\odot y\odot z = (x\odot y)\odot z =\overline{x\oplus y}\odot z = \overline{\overline{x\oplus y}}\oplus z = x\oplus y\oplus z$. (We do not even use the associativity of $\odot$ nor that of $\oplus$.)

Let $n\geq 1$. We can show the following easily by induction on $n$. $$x\_1\oplus x\_2\oplus\cdots\oplus x\_n = (\text{ number of true's in } \\{x\_1,\\, x\_2,\\, \cdots,\\, x\_n\\} \text { is odd }) $$ $$x\_1\odot x\_2\odot\cdots\odot x\_n\\, = (\text{ number of false's in } \\{x\_1,\\, x\_2,\\, \cdots,\\, x\_n\\} \text { is even }) $$

So in general, we have the following, which can be shown directly by induction on $n$ as well. $$\begin{align} \text{for odd } n,\ \ &x\_1\oplus x\_2\oplus\cdots\oplus x\_n = x\_1\odot x\_2\odot\cdots\odot x\_n\\ \text{for even } n,\ \ &x\_1\oplus x\_2\oplus\cdots\oplus x\_n = \overline{x\_1\odot x\_2\odot\cdots\odot x\_n} \end{align}$$

---

Now let us come to the real question. **Why does wolfram alpha give a completely different output for $x\odot y\odot z$ at http://www.wolframalpha.com/input/?i=x+xnor+y+xnor+z**?

As Peter Taylor has noticed on that web page, Wolfram parses "x xnor y xnor z" very differently from what we might have expected, "(x xnor y) xnor z". Wolfram parses it as "Not(x Xor y Xor z)" in text notation or, what is the same, "¬($x \underline\vee y\underline\vee z)$" in symbolic notation. This is not mentioned in its documentation for Xnor operator at http://mathworld.wolfram.com/XNOR.html nor at http://www.wolframalpha.com/input/?i=xnor. One might suspect this is an implementation bug of Wolfram.

However, it turns out this is a feature by design (or possibly an unintentional side-effect) of Wolfram. **Its documentation for Operator Input Forms** shows the following lines, where the small wedges at the end of each line means "built-in meaning exist". So after all **Wolfram has decided to treat "x xnor y xnor z" as "not(xor(x,y,z))" instead of the more common "(x xnor y) xnor z" as a surprise to unsuspecting users such as OP and me**! (Of course, "more common" is only in the eyes of some people. It is quite possible Wolfram's interpretation is more common in other situations.)

One might wonder why Wolfram has made such a strange and uncommon choice. Here is my speculation, my pure shallow speculation.

Wolfram defines Xor for multiple argument as "true if an odd number of its arguments are true and false otherwise", probably along the approach of a BooleanCountingFunction. It also parses and evaluates expressions such as "x1 xor x2 xor x3 xor x4 xor x5" (which everyone agree must be "((((x1 xor x2) xor x3) xor x4) xor x5)") as "Xor(x1, x2, x3, x4, x5)", which is easier to define and faster to compute especially when the number of arguments becomes larger. All is going well without inconsistency for Xnor. Xnor looks very similar to Xor. So, (again just my speculation), **Wolfram chooses to define Xnor in a similar way to Xor** ( and in fact, in a similar way to Or, And, too). Since BooleanCountingFunction only deals with the number of true values, it choose to to define and compute both Xnor(x1,x2,...,xn) and "x1 xnor x2 xnor ... xnor xn" as whether the number of the true values are even, which is also the negation of Xor and which is, at least indeed, the same as x1$\odot$x2 in the case when $n=2$. However, the resulting value of, for example, "x1 xnor x2 xnor x3" as computed by the negation of Xor(x1,x2,x3) is exactly the opposite of the value of "(x1 xnor x2) xnor x3"! In fact, Wolfram's value of "x1 xnor ... xnor xn" and our value of x1$\odot\cdots\odot$xn are the same when n is even and different when n is odd, for any truthy value of x1, ... and xn.

Moreover, there exists a somewhat similar problem for the NAND operator, but to a much less extent since NAND is not associative. Wolfram treats "x nand y nand z" as "x nand (y nand z)" instead of "(x nand y) nand z" (probably for another good reason). You can check the outputs by Wolfram, http://www.wolframalpha.com/input/?i=x+nand+y+nand+z, http://www.wolframalpha.com/input/?i=(x+nand+y)+nand+z and http://www.wolframalpha.com/input/?i=x+nand+(y+nand+z)

In conclusion, **be careful when you use Wolfram to compute logic formula involving XNOR and NAND, especially if you have more than one such operator or more than three arguments**. You will want to double check.
> 2 votes

# Answer
Since $X \odot Y = X \oplus Y \oplus 1$, we see that $$ A \odot B \odot C = A \oplus B \oplus 1 \oplus C \oplus 1 = A \oplus B \oplus C. $$
> 2 votes

# Answer
The discrepancy is that Wolfram Alpha's interpretation of `x xnor y xnor z` is not the same as yours. Compare x xnor y xnor z with (x xnor y) xnor z, looking both at the truth tables and at the logic gate. You consider them to be equivalent, but WA is parsing `x xnor y xnor z` as a single three-input gate `not(xor(x, y, z))`, and it parses `x xor y xor z` as `xor(x, y, z)`, so naturally the outputs are inverted.
> 1 votes

---
Tags: boolean-algebra
---


title: complexity class of functions

text:
# Question
Title: complexity class of functions
What would these statements mean if f(n) and g(n) are functions over natural numbers?

g(n) is in Θ(f(n)). and

An algorithm is in the complexity class Θ(f(n)).

# Answer
> 1 votes
$g(n)$ is in $O(f(n))$ means that there exists a positive number $c$ such that $g(n) \leq c \cdot f(n)$ for all $n$ (or at least all large $n$s). In other words, $g(n)$ does not grow faster than $cf(n)$.

We say "is in" because $O(f(n))$ is a class of all functions that satisfy above condition. It is also sometimes said just "is" and written $g(n) = O(f(n))$ but in my opinion this is too misleading because equality here is not symmetric.

That an algorithm is in a complexity class $O(f(n))$ means that a function $g$ that measures the number of basic calculation steps (dependant of the input size $n$) of this algorithm is in $O(f(n))$.

Useful links:

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


title: What is the peak in fitness landscape

text:
# Question
Title: What is the peak in fitness landscape
I have just started reading about fitness landscapes and I couldn't understand what the peak means. What does the peak mean?

# Answer
It's just the ordinary English-language meaning of the word:

> **peak**, n.
> \[...\] 4 a (1) : the top of a hill or mountain ending in a point
> Merriam-Webster

See, for example, Wikipedia:

> Fitness landscapes are often conceived of as ranges of mountains. There exist local peaks (points from which all paths are downhill, i.e. to lower fitness) and valleys (regions from which many paths lead uphill).
> 2 votes

---
Tags: algorithms, heuristics
---


# Question
Title: Knapsack-like problem oriented on contiguous selection
Problem inputs is an ordered array $A = \[a\_1, a\_2, \ldots, a\_n\]$ with $\text{weight}(a\_i) = w\_i$. We define a $subgroup$ of $A$, denoted by $B$, whose elements' indices are continuous in integer. For example, if $A = \[a\_1, a\_2, a\_3, a\_4, a\_5\]$, then $\[a\_2,a\_3, a\_4\]$ is a subgroup of $A$, while $\[a\_1, a\_3, a\_4\]$ is not. And we say a $subset$ of $A$ is a collection of non-overlapping subgroups of $A$. Our goal is to find a subset $\mathcal{S}$ with $k$ elements in $A$, such that total weight $\displaystyle\sum\_{s \in \mathcal{S}}\text{weight}(s)$ is maximized, while the number of subgroups is less than a given $m$. For example, suppose the corresponding weights of elements in $A$, $\[8,1,6,2,7\]$ and $k=3$, $m=2$, then the optimal is $\\{\[a\_1\], \[a\_4, a\_5\]\\}$.

# Answer
You can use dynamic programming. Define $T^{0}(k\_0,m\_0,i)$- the optimal subset $S$, that uses $k\_0$ elements from the set $\\{a\_i,a\_{i+1},\ldots,a\_n\\}$, includes $a\_i$ uses less than (or equal to) $m\_0$ subgroups. We define similarly $T^{1}(k\_0,m\_0,i)$ but it does no includes the element $a\_i$. We define $W(S)=\sum\_{s\in S} Weight(s)$ for every subset $S$.

For every $k,m\geq 2$ there exists $j\>i$ such that begins with the subgroup $\[a\_{i},a\_{i+1},\ldots, a\_{j-1}\]$. Thus, if we denote $T\_j=\\{\[a\_{i},a\_{i+1},\ldots, a\_{j-1}\]\\}\bigcup T^1(k\_0-(j-i),m\_0-1,j)$ then $T^{0}(k\_0,m\_0,i)$ is the subset with maximum weight among the $T\_j$'s, i.e.,

$$T^{0}(k\_0,m\_0,i)=\arg\max\_{T\_j| \min(n,k\_0+i)\geq j\>i} W(T\_j)$$

In addition, if the first element of $T^{1}(k\_0,m\_0,i)$ is $a\_j$, then $T^{1}(k\_0,m\_0,i)$ equals to $T^{0}(k\_0,m\_0,j)$. Therefore, $$T^{1}(k\_0,m\_0,i)=\arg\max\_{T=T^{0}(k\_0,m\_0,j)|n\geq j\>i} W(T)$$

Note that the initial conditions are $T^{0}(1,m\_0,i)=\\{\[a\_i\] \\}$, $T^{0}(k\_0,1,i)=\\{\[a\_i,a\_{i+1},\ldots,a\_{i+k\_0-1} \]\\}$.

The optimal solution for the problem is the subset with the largest weight among the subsets $\\{ T^{0}(k,m,1), T^{1}(k,m,1)\\}$

We can compute each entry of $T^{0}(k\_0,m\_0,i\_0)$ and $T^{1}(k\_0,m\_0,i\_0)$ in $O(n)$ time. Since there are $O(k\cdot m\cdot n)$ entries of $T^{1},T^{2}$ the time complexity is $O(k\cdot m\cdot n^2)$.
> 1 votes

---
Tags: approximation
---


# Question
Title: What other than programming does a computer science degree usually involve?
Programming courses are about 30% of my computer science degree. Also at my university, around 15-20% of the degree are applied math courses.

What other areas/fields are covered? For the majority of ABET accredited universities?

The question that inspired this post was "should i study computer science if I'm only interested in programming at this point?"

# Answer
A computer science education, among answering a lot of "how?" questions, also covers areas whose purpose is to answer most of the "why?" questions. Those are, in my opinion, the most important, mind-opening and motivating for a future computer scientist with a programming background:

**see comments** for more examples.

Those will give your programming skills a major boost, enrich you with deeper understanding of what's behind the lines of code and thus give you a great advantage when applying for a future job in this area.

Should you study computer science if you are now interested only in programming? I think absolutely yes. You will not lack programming courses for sure, so that's a plus already. Also, you will learn many more interesting things about programming that maybe you haven't yet encountered to figure out that you are interested in them.
> 0 votes

---
Tags: programming-languages
---


# Question
Title: How do I model this expression maximization problem as a Knapsack problem?
Given two arrays of the same length $n$:

$A = \\{a\_1,a\_2,\dots,a\_n\\}$,

$B = \\{b\_1,b\_2,\dots,b\_n\\}$,

I have to maximize the following expression:

$$\frac{a\_{i\_1} + a\_{i\_2} + a\_{i\_3}+ \dots + a\_{i\_k}}{b\_{i\_1} + b\_{i\_2} + b\_{i\_3}+ \dots + b\_{i\_k}}$$

Where $k \lt n$.

**Given the constraints:**

Firstly, when you select a particular $a\_i$ you have select it's corresponding $b\_i$, and vice versa.

Secondly, you have to select exactly $k$ elements from the arrays. Where $k \lt n$.

**Assumptions:**

The assumption is that $A$ and $B$ both contain natural numbers only.

**What I have tried:**

I have tried sorting the arrays using the ratio $\frac{a\_n}{b\_n}$ in the non-decreasing order, but this gives an incorrect result since it's trying to optimize $\frac{a\_1}{b\_1} + \frac{a\_2}{b\_2} + \dots \frac{a\_k}{b\_k}$. That is different from my desired objective function.

I have also thought of treating the denominator as a knapsack but this does not make sense because there are no weights involved.

**Any suggestion on what I can do to model this problem as a knapsack optimization problem?**

# Answer
> 1 votes
One approach (not based on the knapsack problem): suppose you are given a threshold $\tau$ and want to check whether you can find a subset such that

$$\frac{a\_{i\_1} + a\_{i\_2} + a\_{i\_3}+ \dots + a\_{i\_k}}{b\_{i\_1} + b\_{i\_2} + b\_{i\_3}+ \dots + b\_{i\_k}} \ge \tau.$$

Could you solve that problem? If you could, you could use binary search on $\tau$.

Note that the above condition is equivalent to

$$a\_{i\_1} + a\_{i\_2} + a\_{i\_3}+ \dots + a\_{i\_k} \ge \tau \cdot (b\_{i\_1} + b\_{i\_2} + b\_{i\_3}+ \dots + b\_{i\_k}),$$

or equivalently,

$$a\_{i\_1} - \tau b\_{i\_1} + a\_{i\_2} - \tau b\_{i\_2} + a\_{i\_3} - \tau b\_{i\_3} + \dots + a\_{i\_k} - \tau b\_{i\_k} \ge 0.$$

And that enables us to find a simple way to check for the existence of that subset.

See if that gives you any ideas.

---
Tags: algorithms, optimization, knapsack-problems
---


# Question
Title: Knuth's Algorithm X - why do we backtrack rows but not columns?
Knuth's Algorithm X (described here in more details) prescribes that we select a column deterministically (but arbitrary), when we backtrack rows we do not backtrack columns, so we do not have an opportunity, to "rewind", select a different column and try again, during the course of the algorithm.

How can we be sure, that we find all solutions if we do this, and don't miss a few? Or did I get this wrong, and the algorithm cannot actually find every solution? Reading the research paper linked above I got an impression, that it is able to find / enumerate all the solution. So what makes sure we do not miss some of these?

# Answer
> 2 votes
No, it is not necessary to backtrack the columns.

Take an arbitrary solution $X = \\{\text{some row indices}\dots\\}$. In the first step the algorithm picks some column $j$, and in the second step it iterates over all rows $i$ with $A\_{ij} = 1$, makes the matrix smaller and recursively calls itself for each such row.

Since $X$ is a valid solution, there exists some $i\_0 \in X$ with $A\_{i\_0 j} = 1$. Let's analyze the iteration step, in which the algorithm chooses the row $i\_0$. How does the matrix change?

* It removes all columns $k$ with $A\_{i\_0 k} = 1$: this doesn't bother us. $X / \\{i\_0\\}$ is still a valid solution for the smaller matrix.
* It removes all rows, that have at least one set $1$ in a same column as row $i\_0$: this still doesn't throw away any important stuff. Because we know that all rows in $X$ have the $1$s in different places. So still all rows of the solution will be part of the smaller matrix.

As you see, it doesn't matter how the algorithm picks the column (any choice of column is possible), you will still find a row, that is part of your solution, the solution is still a solution of the smaller matrix. And by induction, we the algorithm will find the solution. Just the order of the rows of the solutions will differ, if we pick some other column. But we will find the same solutions.

# Answer
> 2 votes
We need to ensure that, in each column, we have chosen at least one entry (one row) that contains a 1. It doesn't matter what order we consider the columns in; any such order will give us a valid solution.

For example, suppose we first choose a row for column 1; then we choose a row for column 2. That will explore all possible solution. Alternatively, you could first choose a row for column 2, then choose a row for column 1; but that will give the same set of solutions, just in a different order (because a solution describes which row you chose for column 1 and which row you chose for column 2).

---
Tags: algorithms
---


# Question
Title: Rows and columns in quantum-gate matrices read the same - why?
I have noticed that for all the matrices representing quantum gates, if we read rows left-to-right and top to bottom, the read the same as columns top to bottom left to right.

Example:

\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1& 0 \end{pmatrix} (CNOT gate), if we read the values in from the first row, we see `1 0 0 0`. Similarly if we read left-most column top to bottom. Second row reads `0 1 0 0`, just like 2nd left column etc.

I believe this is a property of all matrices representing quantum gates, but cannot explain why exactly this is the case (and if it is, in fact, guaranteed for every quantum gate?)

# Answer
> 2 votes
A counter-example to your observation is the Pauli Y gate:

$$Y = \begin{bmatrix} 0&-i\\i&0\end{bmatrix}$$

The first row is 0 then -i, but the first column is 0 then +i.

Another example is the X-\>Y-\>Z-\>X gate (a 120 degree rotation around the X+Y+Z axis of the bloch sphere):

$$\frac{1-i}{2} \begin{bmatrix} 1&-i\\1&i\end{bmatrix}$$

---

The reason the rows often look so much like the columns, particularly for self-inverse operations, is because quantum gates are unitary and the inverse of a unitary matrix is its conjugate transpose. But you can easily break the symmetry by multiplying an individual row (or column) by a phase factor, which produces a different but valid quantum operation.

---
Tags: quantum-computing, matrices
---


title: quicksort recurrence relation

text:
# Question
Title: quicksort recurrence relation
In Concrete Mathematics Textbook by Donald Knuth and Oren Patashnik , ch.2 Sum ,sec2.2
He wrote:

> The average number of comparison steps made by quicksort when it's applied to $n$ items in random order satisfies the recurrence : $$C\_0=0;$$ $$C\_n = n + 1 + \frac{2}{n}\sum\_{k=0}^{n-1}C\_k$$

The question is how he get the relation :

$$C\_n = n + 1 + \frac{2}{n}\sum\_{k=0}^{n-1}C\_k$$?

# Answer
> 2 votes
Unfortunately, that textbook says nothing about how to deduce that particular recurrence relation, although it has plenty of examples on how to obtain a recurrence relation. In fact, I cannot understand $C\_1=1+1+C\_0 =2$, which says that we need two comparisons to sort 1 item using quicksort.

If OP's intention is emphasizing how **he** (meaning them, Donald Knuth and Oren Patashnik) get the recurrence relation, then I can only honestly say I have no credible idea beyond a few educated guesses.

If OP's intention is just to know how to deduce the recurrence relation, then the wikipedia item on quicksort is a nice answer, which I have copied below with minor modification to fit current question.

> Assume that there are no duplicates. When the input is a random permutation, the rank of the pivot is uniform random from 0 to $n − 1$. Then the resulting parts of the partition have sizes i and $n − i − 1$, and $i$ is uniform random from 0 to $n − 1$. So, averaging over all possible splits and noting that the number of comparisons for the partition is $n − 1$, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the following recurrence relation.

$$ C(n)=n-1+{\frac 1n}\sum\_{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac 2n}\sum \_{i=0}^{n-1}C(i) $$

Please note that in the wikipedia item, $C(1)=1-1+0=0$, which say that we need no comparison to sort 1 item, which looks much more reasonable to me

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation, quicksort
---


# Question
Title: Why can't we just use preorder traversal to check if a tree is subtree of binary tree?
Is preorder traversal enough to check if a tree is subtree of a binary tree?

Are there any scenarios which I can miss if I use just the preorder traversal?

What other methods can be used to check if a tree is subtree?

Also, what happens if my binary tree contains non-unique values at nodes?

# Answer
> 2 votes
Because different trees can have the same pre-order label sequence (easy exercise).

To check equality, recurse on both trees at the same time. That gives you a simple (if not terribly efficient) algorithm for checking whether a tree is a subtree of another one.

# Answer
> 0 votes
You can use the following algo to check whether tree SMALL is a part of tree LARGE:

1. Compute height of smaller tree: small\_height = height(SMALL)
2. Recurse large tree, computing height in each node
3. If node height is the same as small tree height, compare trees:

`recurse(tree)
 left_height = recurse(tree.left)
 right_height = recurse(tree.right)
 height = max(left_height,right_height) + 1
 if height==small_height
 compare_trees(SMALL,tree)
 return height`

Time analysis is simple: you may visit each node in large tree once or twice - once when computing height and another time when comparing it to small tree. So, browsing large tree is O(n), and computing height of small tree require to visit each node so it's O(m).

---
Tags: algorithms, trees, binary-trees
---


# Question
Title: Is there a poly-time algorithm for expanding out polynomials
so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of $$ z = (x+y)(x-y) \implies x^2+xy-xy+y^2 $$ but for any input with $n$ number of operations. $$ z = (x\_1+x\_2+x\_3+...+x\_n)\cdot(x\_1+x\_2+x\_3+...+x\_n)\cdot...\cdot(x\_1+x\_2+...x\_n) = ? $$

I tried just doing the basic "by hand" method, but to me that seems like it would be on the scale of $n!$. Is there a better way of doing this? Thank you!

# Answer
For the particular polynomial in the question, we have the multinomial theorem. $$ (x\_1+x\_2+\cdots+x\_n)^m = \sum\_{k\_i\geq 0,\\, k\_1+k\_2+\cdots+k\_n=m} \binom{m}{k\_1,k\_2, \cdots,k\_n} x\_1^{k\_1}x\_2^{k\_2}\cdots x\_n^{k\_n}$$ where the coefficients are knowns as multinomial coefficients, and can be computed by $$ \binom{m}{k\_1,k\_2,\cdots,k\_n} = \frac{m!}{k\_1!\\,k\_2!\cdots k\_n!}$$

For most of general products of multivariable polynomials, there is no such closed formula for their expansion.
> 2 votes

---
Tags: algorithms, polynomial-time, mathematical-programming, program-optimization
---


# Question
Title: A 4-bit combinatorial circuit that outputs 1 when integer greater than 7 and is odd number
I need to draw a combinatorial circuit that when an integer is greater than 7 and is an odd number, the output will be 1. There are 4 inputs representing 4 bits and 1 output wire. The output wire is only 1 if an integer is greater than 7 and is an odd number.

My attempt: If I segment the 4-bit input as r x y z where if the input was 8, the 4-bits would be 1 0 0 1. I know that r and z must have an AND gate but cannot figure out a way to get x y to work. I drew a truth table and found that

* 1 0 0 1
* 1 0 1 1
* 1 1 0 1
* 1 1 1 1

must all equal to 1 to satisfy the condition placed. Any help is appreciated.

# Answer
You've got the answer!

The number is eight or higher if the first bit is set. The number is odd if the last bit is set. So the answer is simply those two bits ANDed together. The two middle bits don't matter, you don't need to bother with them.
> 1 votes

# Answer
Greater than $7$ along with being odd implies numbers $9, 11, 13, 15$ which you have already listed out. Going by the bit pattern generated, the resulting circuit consists of only $r . z$. You won't need to check for other even numbers $\>=8$ since they have $z$ bit as $0$, and numbers smaller than $8$ will ahve $r$ bit as $0$ and will thus output $0$.
> 0 votes

---
Tags: logic, combinatorics
---


# Question
Title: Ordering the incident edges of each vertex to have a specified pre-order traversal
**Input**: You are given a graph $G(V, E)$ undirected, loop-less, no parallel edges, etc. and a label function $L: V \to \mathbb{N}$. Also, a sequence of $|V|$ natural numbers is given.

**Output**: Is it possible to order the incident edges set of each vertex and choose a starting vertex $s \in V$ so that a *pre-order DFS traversal* starting from $s$ prints out a sequence of labels of visited vertices which matches the given sequence.

Any idea on this problem? It is solvable on trees by **Dynamic Programming**. But for general graph, it seems to be much harder.

# Answer
> 0 votes
We reduce from Hamiltonian cycle. Given a graph $G$, we construct new labelled graph as follows:

* Label each vertex of $G$ by $\mathrm{A}$
* To each vertex of $G$ connect it with a hanging vertex "above" it and label this vertex by $\mathrm{F}$
* For each edge $e$ of $G$, add a "middle" vertex labelled by $\mathrm{K}$, and connect each "middle" vertex to the two $\mathrm{F}$ vertices above the two $\mathrm{A}$ end points of its corresponding edge.

The sequence will be $\mathrm{AFKAFK}\dots\mathrm{AFK}$$KKK..\dots KKK$ where we repeat the pattern $\mathrm{AFK}$ the number of times equal to the number of vertices of $G$, i.e. $|V(G)|$. And the number of trailing $\mathrm{K}$ (*written in italic for clarity*) equals $|E(G)|-|V(G)|$, i.e. after finishing the Hamiltonian cycle, the traversal needs to come back and collect the remaining "middle" vertices.

If $G$ is Hamiltonian, clearly we can order the neighborhood of each vertex so that the edge that will be taken at each vertex is in accordance with the Hamiltonian cycle.

Conversely, if we can order the neighborhood of each vertex and choosing a string vertex so that the preorder traversal prints out the required sequence then we can follow the path delineated by the traversal to figure out the Hamiltonian cycle. Indeed, if at some point you get stuck, then there would be the very FIRST time you get stuck somewhere. But clearly, if so, you need to produce a $\mathrm{KK}$ before the trailing "garbage" sequence begins. In short, you cannot get way back and branch (at least for the FIRST time) without printing out a $\mathrm{KK}$.

---
Tags: np-complete, graph-traversal
---


# Question
Title: Counting (enumerating) minimal solutions of a dual horn formula
Is there an efficient algorithm ("does not necessarily have to be a polynomial time algorithm") to compute all "minimal" solutions for a Dual Horn formula (conjunction of clauses where each clause contains at most one negated literal)? By "minimal" I mean, consider the following dual horn clause (formula)-: $x\_1 \lor x\_2$. While the solutions are $(1,0), (0,1), (1,1)$, we do not consider $(1,1)$ to be minimal since negating any bit in $(1,1)$ will also yield a feasible assignment. More generally, by a minimal solution I mean given a solution $S$, let $X$ be the subset of variables in $S$ that have been set to true, then if there exists a proper subset in $X$ which alone when set to true also satisfies the original dual horn formula, then $S$ is not minimal.

Further, it would be great if someone can point me to literature on the same.

Here are my thoughts on the problem, and admittedly not thoroughly thought true. I understand that since Horn SAT has a linear time algorithm for finding a feasible assignment, Dual Horn also must have such an algorithm analogously. However, Dual Horn can have more than 1 mimimal solution as shown in my example above whereas Horn has a single minimal solution.

On the problem of enumerating all minimal solutions, if in case the linear time algorithm is able to output at least one minimal solution, then an obvious way to enumerate other mimimal solutions would be to add another clause cutting off the previous solution. However this I suspect is likely to break the dual horn structure in the formula and also it is obviously inefficient to do so. Hence, I think there could be a better algorithm to enumerate them. An alternative algorithm may be to do a branch approach, where after a solution has been computed we branch on one of the variables and repeat the linear time algorithm, however now we may have preserved the dual structure in the formula.

As D.W pointed out below there can be exponential number of solutions. However I suspect there could be a way to enumerate all minimal solutions in the dual HORN formula based on some notion of the structure(relationship between variables and clauses). I am most interested in knowing if there exists an algorithm that exploits the structure in the problem for enumeration. By "EFFICIENT" this what I mean.

# Answer
Since Horn and Dual Horn are analogous, yet opposite, your definition of minimal for Horn would be the negation of the Dual Horn definition. Said another way, if you negate the definition of minimal DualHorn, by your thinking, there is only 1 minimal solution.

Although, I'm not following the logic entirely.

There are papers on counting solutions to Horn or Dual Horn and it had been shown (proven?) to be NP.
> 0 votes

---
Tags: satisfiability, counting
---


# Question
Title: Page cache and its relationship to page table
I was reading about the page cache Page cache \- the cache in memory for files, but I couldn't find the answer to my question. Does the page table have anything to do with, or maintain any entries, for the page cache? My guess is no, despite the similar sounding name, as the page table only stores entries for text/code, stack, and heap segments for a process (i.e., virtual memory).

# Answer
> 1 votes
The only link is that they both operate with the same page size and, well, the same pages.

The reason is the mechanism of file access. You can request access to file via mapping its contents into memory space. In this case, the entire file isn't read into memory at once, instead, the page table is filled with inaccessible pages. Once application tries to access these pages, the actual file contents is read into memory.

So, the file cache stores individual pages of files, and this mechanism is described in the page cache article.

---
Tags: memory-management, storage
---


# Question
Title: How does SpaCy make its dependency tree?
I discovered that SpaCy had the ability to make dependency trees. For instance given a question *“To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?”*

We can create its dependency tree with the following code :

I know that it is a set of edges $E$ which represents the relations of labeled dependencies of the particular analysis of $G$. More precisely, an edges $w\_i, r, w\_j \in E$ represents a relationship of dependence of head $w\_i$ towards $w\_j$ labeled with the type of relationship. A dependency graph $G$ is therefore a set of dependency relations between tokens in $S$.

For instance we present the dependency graph that follows by the following graph:

* $G = (V, E)$
* $V = \\{\mbox{It, is, a, replica, of, the, grotto, at, Lourdes, France, where, the, Virgin, Mary}\\ \mbox{reputedly, appeared, to, Saint, Bernadette ...}\\}$
* $E=\\{\mbox{(is, NSUBJ, It), (is, ATTR, a replica), (a replica, PREP, of),...}\\}$

**But I was wondering how does $E$ was made with Spacy? How does the dependency tree method chose which node is the root and which aren't?**

I have heard from this French paper that, on the one hand that $E \subseteq V \times R \times V$ where $R = {r\_1, ..., r\_m}$ is a finite set of dependency possible names that we call dependency relationship. They can link two tokens in a sentence. A dependency name $r \in R$ is also called a labeled edge. For example, a relationship between a head verb and its subject can be noted with $r = SBJ$.

On the other hand it was an analysis problem of finding the dependency graph that has the highest score for an input sentence.

Yet I haven't seen where there is a child-children ordering creation.

---

The context is that I am using SpaCy dependency trees to get the root of sentences of a paragraph and match it with the root of a question.

For the question given above we have to find the answer in the following paragraph :

> Context — “Architecturally, the school has a Catholic character. Atop the Main Building\’s gold dome is a golden statue of the Virgin Mary. Immediately in front of the Main Building and facing it, is a copper statue of Christ with arms upraised with the legend “Venite Ad Me Omnes”. Next to the Main Building is the Basilica of the Sacred Heart. Immediately behind the basilica is the Grotto, a Marian place of prayer and reflection. It is a replica of the grotto at Lourdes, France where the Virgin Mary reputedly appeared to Saint Bernadette Soubirous in 1858. At the end of the main drive (and in a direct line that connects through 3 statues and the Gold Dome), is a simple, modern stone statue of Mary.”

The expected answer is *“Saint Bernadette Soubirous”*. The sentence having the answer — is *“It is a replica of the grotto at Lourdes, France where the Virgin Mary reputedly appeared to Saint Bernadette Soubirous in 1858”*. Its dependency tree of the sentence containing the answer is :

# Answer
Matthew Honnibal, who created Spacy, answered me :

> The full answer is rather complicated :). I've written a few blog posts over the years to make it more accessible. The best place to start is this blog post:
>
> https://explosion.ai/blog/parsing-english-in-python
>
> Since v2, we use a more complicated machine learning strategy, following the general architecture described here: https://explosion.ai/blog/deep-learning-formula-nlp . More specifics about the model architecture can be found in this description of the NER model: https://www.youtube.com/watch?v=sqDHBH9IjRU
>
> The transition system is mostly described by this paper: http://aclweb.org/anthology/D15-1162 , but with some modifications for sentence segmentation.

I already started with the first one which I didn't completly understand yet. I will update this post through my reading progress but leave the question open if a concise question comes to your mind.
> 4 votes

---
Tags: trees, parsers, natural-language-processing
---


title: QTM & Halting problem

text:
# Question
Title: QTM & Halting problem
"Can QTM (Quantum Turing machine) solve halting problem" Why not have an immediate answer "No QTM Can't do this", we know that Turing proved it impossible when DTM , i meant , " Why we cant use the same proof which turing use it" Let H be a program in a quantum turing machine that will solve the issue of halting , why not say that a contradiction will occur Thanks

# Answer
Because we can simulate QTM with DTM and it is an easier proof method than proving directly for QTM (which we can do). Also, this method of simulating a model with DTM to prove they are equivalent in power is somewhat a standard tool, not just for various TMs, but also for other computaitonal models ($\lambda$-calculus, RAM-machines,$\ldots$)

I think this question and answers address everything else you may be wondering
> 3 votes

---
Tags: turing-machines, quantum-computing
---


# Question
Title: How to transform lambda function to multi-argument lambda function and how to rewrite or approximate terms?
I am trying to do the formal semantics (Montague grammar, abstract categorial grammar) of natural language and encode the sentence `John is boss`. The type system has to primitive types - `e` for entity and `t` for Boolean type. `John` has type `e`, `is` has type `(e->t)->(e->t)` and `boss` has type `(e->t)`. The the full sentence is translated as the lambda expression:

```
(is(boss))(John): t

```

I don't like the chaining of functional application and more intuitive presentation could be by introducing new function `IS` of type `(e, (e->t))` and hence the expression could become:

```
IS(John, boss): t

```

And by moving boss from the argument the function index we can arrive to the standard predicate expression with new predicate-function:

```
IS_BOSS(John): t

```

I have two questions regarding this example:

* Does standard lambda calculus have multi-argument functions? As I guess that these calculus have such function by currying and hence the real type if `IS` is `e->(e->t)->t`. So, this part seems to be already answered.
* And now is the main question - **does lambda caluclus allow do function transformation** \- e.g. is there some operation which transforms `is:(e->t)->(e->t)` into `IS:e->(e->t)->t`? **Are there some apparatus/algorithms/methods how can I express function** `is` **via the function** `IS` **and how can I transform terms involving** `is` **into terms that does not contain** `is` **and that contains** `IS`**?** Are there some rewriting apparatus available for this in lambda calculus?

This question is inspired by the book https://www.amazon.co.uk/Elements-Formal-Semantics-Introduction-Mathematical/dp/0748640436 and uses notions and notation from this book.

Important note. I do not expect that `is` and `IS` are identical functions (but I would be glad to consider the case when some kind of identity is assumed as well). I expect that `is` is more general function (that is used for the processing of the raw text) and that I try to express it using more specialised function `IS` (which can convey more specific meaning, e.g. borrowing from pragmatics (branch of lingustics): I can analyse context and determine that in this context such detalization is desirable). Maybe rewrite operation should be used but maybe some other tools should be used - simply - how to transform term using these functions? **Maybe I am just trying to approximate function** `is` **with function** `IS` **(of different type!) and** `is`**-terms with** `IS`**-terms? Are there such notions, theories?**

*Maybe I should look to higher-order rewriting of lambda terms? Is there example available how my terms could be rewritten inside such framework?*

# Answer
> 4 votes
You are looking for currying and uncurrying which transform functions of type $A \times B \to C$ to functions of type $A \to (B \to C)$, and vice versa. Currying takes `IS` to `is`, while uncurrying takes `is` to `IS`. This is a standard and very basic technique in $\lambda$-calculus. There are many manifestations of currying and uncurrying, for instance in arithmetic it is the identity $c^{a \cdot b} = (c ^ b) ^ a$.

It is largely a matter of taste how you write multi-argument functions. The uncurried form $A \to (B \to C$ has the advantage that you can apply the function only to the first argument. In your case `is boss` is a useful concept which is expressible very neatly. With the other function you have to write `λ x . IS (boss, x)`.

Note however that sometimes people do *not* include product types $A \times B$ in their versions of $\lambda$-calculus, in which case of course currying is unavailable (but nothing much is lost).

---
Tags: formal-grammars, lambda-calculus, natural-language-processing
---


# Question
Title: Virtual Address and Physical Address Space
A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8K. How many entries are needed for a conventional page table ?

The answer is 2^35 entries

Why not (2^32) / (2^13) = 2^19 entries...?

My doubt here is why does the number of page table entries depend on virtual address space rather than physical address space?

What does it mean to have more virtual address space than physical address space? The process can only access as many pages present in the physical memory. So it makes sense to have same have both virtual and physical memory address space same. But why have more virtual address space? Does it mean 2 different virtual address entries are mapped to the same physical location in the same page table? Guess that would lead to inconsistency right? Can someone help me get the bigger picture here..... I really need to internalize this concept.

# Answer
> 3 votes
When we are using Virtual Memory, we are translating from a Virtual Address Space to a Physical Address Space.

To understand why it requires $2^{35}$ entries, consider the page size. In order to byte address $8$KB, we require $2^{13}$ entries. If we consider the Virtual Address given to us of $48$ bits, this gives us $48-13=35$ bits. These are the bits that are used for indexing into the page table for determining the address of the page or 'frame' in main memory.

The reason for having more virtual memory is because programs were getting so large that they couldn't be fit in main memory. So in order to allow a greater degree of multiprogramming, virtual memory was introduced. A program could have a 'large' memory to itself. However only the required parts would be loaded into memory as and when required a concept refered to as Demand Paging.

# Answer
> 0 votes
**Why not (2^32) / (2^13) = 2^19 entries...?**

Page table is organized as per number of pages and not frames.

i.e. 2^48/2^13=2^35

But if you are using inverted page table then reverse mapping will be done and table will be organized as per number of frames.

i.e. 2^32/2^13=2^19.

**The reason for having more virtual memory**

The main objective is to increase the degree of multi programming i. e. ability to interact will multiple processes though we have insufficient amount of physical memory.

# Answer
> 0 votes
As we know `|pageAddress|Offset| -> |Virtual Address|`.

Pages are **8K i.e 8\*1024 = 2^13 bytes**.

This implies that it needs 13 bits as offset value . And higher **(48-13 = 35)** bits for size of page address. So, total **2^35** entries in page table.

Note: if n bit of page address then there are altogether 2^n entries in page Table.

---

**My doubt here is why does the number of page table entries depend on virtual address space rather than physical address space?**

Virtual Memory which is divided into fixed sized block is called pages. CPU deals with only virtual address which is not actual memory address and not real exist. The physical memory is divided into number of fixed size block is called page frames and it has physical address.

Every time to access memory content Memory management Unit (MMU) convert virtual address to Physical address.

Visit this link

---
Tags: operating-systems, memory-management, virtual-memory, paging
---


# Question
Title: How does hash table search scales with number of keys?
Say, I have one of the standard implementations of a hash table: chaining or open addressing, and my hash key is a pair of strings. Instead of using the hash table with the pair as a key, I can use the first key to get to a "sub" - hash table, and then use the second key to find the element from it.

How do these strategies compare, e.g. if one assumes the key pairs are more or less uniform?

# Answer
> 1 votes
In principle, they're similar in running time and space complexity.

In practice, the first one might have some modest advantages: possibly half as many accesses, less space overhead if some of the "secondary hashtables" were small (e.g., for a particular value of the first key, there aren't many possible second keys).

I would not expect to see a tremendous difference between the two, nor a difference in asymptotic worst-case running time. Both have $O(1)$ expected running time for all major hash table operations, under some reasonable assumptions.

# Answer
> 1 votes
A well tuned hashtable (in terms of when you grow the table and collision handling) with a good key distribution will stay constant time.

If the second level is a lot faster than the top level it may be worth adding it.

For example Google uses a hashtable that uses open addressing and hold 1 byte of hashkey per element. Using SIMD you can check 16 bytes (or more depending on the SIMD instruction set) against part of the key in a single operation and also check whether you need to move to the next chunk of 16 elements.

But if you are just going to use the same implementation for the second level you are not going to win anything.

# Answer
> 1 votes
How large are your secondary tables? Depending on your data, the secondary tables might have on average not much more than one element. Some implementations don’t bother doing any hashing for small numbers of elements, say up to three. Just store them in a small array. This may be a lot more efficient than a full blown hash table.

How much hashing do you need to do? You may have one key that is in practice close to unique, and the faster hashing may outweigh any disadvantages.

---
Tags: hash-tables
---


# Question
Title: Algorithm for printing all accepted strings (to an upper bound if infinite amount) from a given DFA
As the title states I'm trying to write an algorithm that generates accepted strings to an upper bound from a given DFA.

It should not generate more strings than the upper bound n if it contains cyclic patterns, because obviously I can't print an infinite amount of strings, which leads me to my problem.

Machines with finite languages are very straight forward as I can just do a DFS search and traverse through the graph and concatenate all letters that connect the states recursively, but I have no clue how I should deal with infinite language DFAs unless I hardcode a limit on how many times the DFS should traverse states that can potentially lead to cycles.

So my question is; how should go about approaching this problem. Are there any known algorithms (aside from DFS, BFS) that I could use to tackle this task?

Thanks in advance. I tried hard to find similar questions but I couldn't find anything helpful.

Edit: Clarified problem a little bit.

# Answer
> 1 votes
The simplest one is to generate all strings up to length n and test them against the DFA.

The next option is a Breadth first traversal over the DFA (emitting the string each time you encounter a final state) however this can need a lot of memory. In the worst case all you need to keep all of length `n` in memory.

Next is a depth first traversal up to length `n`. Keep a counter of how long the string would be and backtrack when you exceed `n`.

To instead get the first n strings you run one of the above algorithms with a certain length and if it generates not enough strings you increment n until it does.

# Answer
> 1 votes
The essence of this problem is to search the possibly-infinite transition tree induced by the DFA. Each node in this tree consists of a state and a string (the prefix of a recognised sentence). For each possible transition from the state, there is a child node consisting of the target state and the string augmented with the transition character. The target strings are those belonging to nodes whose states are accepting states.

I think this assignment is probably intended to get you to understand recursion with back-tracking, since there is a pretty simple solution: recursively (depth-first) walk the transition tree, failing if the recursion depth reaches the limit on string length. (If strings can be long, you might want to use an explicit stack rather than recursion to avoid stack overflow.)

That is not, in my opinion, the best solution to this problem. I'd use a breadth-first search limited to the number of strings you need to find. However, if you do choose to implement the recursive backtracking solution, I do recommend that you do useless state elimination as suggested by \[Note 1\]; otherwise, a self-looping dead state (with at least two loops) will produce exponential slow-down during the DFS.

Let's recall that the basic breadth-first algorithm involves the use of a queue of transition tree nodes. We initialise the queue with the root node ($\<start, ""\>$) and then, as long as the queue is non-empty and we have not found enough solutions, we do the following:

```
1. Remove the first node from the queue
2. If that node has an accepting state, report the string as a solution.
3. Append all possible transitions from that node to the end of the queue.

```

The result of this algorithm is that solutions will be generated in order by length, shortest strings first.

The problem with breadth-first search, as I gather you discovered through experimentation, is that if the branching factor is high and several transitions are required before an accepting state is found, then the queue expands to an exponential size (and that takes exponential time).

However, not all of the queue is necessary, since the number of target strings is known in advance. If we assume that the DFA has no useless states \[Note 1\], then every node in the transition tree is either a solution or has at least one solution in its subtree. Consequently, the maximum useful size of the queue is the number of solutions we require. When the queue has reached this size, we just don't do the append. When we find a solution, we can reduce the size limit by one.

Imposing this limit on the queue size removes the possibility of exponential time blow-up, but a naïve implementation no longer guarantees that the solutions found are the shortest solutions. This introduces an inefficiency, and even a possible error (because in pathological cases we might reach the string size limit before finding enough solutions, even though shorter solutions exist).

As a fix, we can track the levels during the BFS walk, reordering the traverse of each level. In this version, we use two queues, one for the current level, from which we pop nodes, and one for the next level, onto which we push newly found nodes. Every time the current queue becomes empty we've finished a level; we then swap the two queues. If both queues are empty, there's nothing more to be done.

Now we're not limited to processing the queue for a level from left-to-right; we can process it as we see fit, as long as we do all of it before moving on to the next node.

For a first approximation, we can ensure that we don't lose any accepting states. When we push a new node onto the next level:

* If it is an accepting node, we push it onto the beginning. If the queue is full, we push the new node anyway, popping the last node.
* If it is not an accepting node and the queue is not full, we push it at the end.

That still won't guarantee that all shortest strings are produced, but it should be sufficient in most cases. It can be improved by sorting the next-level queue by the minimum distance from each state to an accepting state. The minimum distances for each state can be precomputed with a simple breadth-first search over the DFA, which will also serve to eliminate useless states

---

### Notes

1. Here I'm using the phrase "useless state" in a possibly non-standard way. By "useless state" I mean a state which does not appear in any transition sequence ending at an accepting state. In other words, for a state to be useful, it must be

* reachable from the start state
    * accepting, or able to reach an accepting state

If that's not guaranteed in the DFAs you're begin given, it is easy to guarantee by detecting and removing useless states.

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


# Question
Title: Exponential nested Loop Big O complexity calculation
Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with this particular piece of code to get BIG O but i can't mathematically..... I'm a newbie.

I tried to logarithmate the whole thing like: j= n, n^(1/2), n^(1/4), ........, 2 then:

j= log (2,n), log(2, n^(1/2)), ..... log (2, (n^(1/2))^K) *need to find out K from this notation*

If i try to sum them up: log(2,n) + 1/2\*log(2,n) + 1/4\*log(2,n) + ..... + (1/2)^K * log(2,n)

then:

log(2,n) * \[1/2 + 1/4 + ....... + (1/2)^K\] The number of terms this sum has should give me the number of steps for j I can't proceed to i without it but i get stuck right there at that sum at this point and i get lost from here.....

I also made a piece of code to count the steps and have a better view here are the results for

n = 1000

for j: 1000 i: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1, steps: 10

for j: 31 i: 31, 15, 7, 3, 1, steps: 5

for j: 5 i: 5, 2, 1, steps: 3

for j: 2 i: 2, 1, steps: 2

n = 65

for j: 65 i: 65, 32, 16, 8, 4, 2, 1, steps: 7

for j: 8 i: 8, 4, 2, 1, steps: 4

for j: 2 i: 2, 1, steps: 2

```
for (int j=n; j>1; j=sqrt(j))
       for (int i=j; i>0; i/=2)
             k++; // O(1)

```

# Answer
Let n = 65,536 and write down what exactly happens. That should be enough to figure it out.
> 0 votes

---
Tags: algorithm-analysis, asymptotics, loops
---