# Question
Title: How to find the smallest $r$ such that $o_r(n) > \log^2(n)$ in polynomial time?
Defining $$ o\_r(n) = \min \left\\{ \hspace{1mm} k \in \mathbb{N} \hspace{2mm} | \hspace{2mm} n^k \equiv 1 \hspace{3mm} (\text{mod } r) \hspace{1mm} \right\\} $$ How can we show that finding the smallest $r$ such that $o\_r(n) \> \log^2(n)$ can be done in polynomial time?

# Answer
It appears you are asking because you are interested in understanding the famous "PRIMES is in P" paper and why its algorithm runs in polynomial time. Finding such an $r$ is exactly step 2 of their algorithm.

As was explained to you previously on Math.SE, the paper explains why its algorithm runs in polynomial time. The explanation is terse and assumes the reader will be able to make the missing connections, but the key ideas are there. If you keep reading in the paper it presents the crucial fact: the smallest such $r$ has size at most $r \le \max\\{3, \lceil \log^5 n \rceil\\}$ (see Lemma 4.3, which is just a few paragraphs after the statement of the algorithm). Consequently, there is a very simple algorithm to find such an $r$: try each $r$ in turn, i.e., try $r=1$, then $r=2$, then $r=3$, checking each candidate value of $r$ to see if it satisfies the condition. Output the first one you find that satisfies the condition. Thanks to the fact in the paper, you'll only need to try $O(\log^5 n)$ many such $r$, which is polynomially many. Moreover, you can check the condition for a given $r$ in polynomial time. Thus, the total running time is polynomial in $\log n$.

In the future, if you have a question about some aspect of the paper, please tell us in the question what paper you are reading. More generally, tell us about the context around your question and the motivation. Also, when asking about some aspect of a paper, I encourage you to read the entire paper before asking -- sometimes the answer to your question might be found later in the paper.
> 1 votes

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


# Question
Title: The set of all eventually periodic words is not Buchi Recognizable?
An $\omega$-word $s \in \Sigma^\omega$ is eventually periodic if it is of the form $s = uv^\omega$ for finite words $u, v \in \Sigma^\*$.

I want to show that the set of all eventually periodic words is not buchi-recognizable.

I do not know how to proceed. My attempt was to find a part of the word and then pump it indefinitely to get something that is not in the language. However, pumping right away does not seem to work since that would give an eventually periodic string again.

# Answer
Note that every non-empty Büchi recognizable language contains at least one eventually periodic word and that the class of all Büchi recognizable languages is closed under complement. Thus, if the language $L = \\{w \in \Sigma^\omega \mid w \text{ is eventually periodic}\\}$ was Büchi recognizable its complement $L^C$ is also Büchi recognizable but of course contains no eventually periodic word contradicting the first fact I stated.
> 3 votes

---
Tags: strings, buchi-automata
---


title: Solve every problem with recursion

text:
# Question
Title: Solve every problem with recursion
Is it possible to solve every problem (solvable with turing machine) with only recursion ? If yes, which principles or theories assure this ? Thanks

# Answer
> 0 votes
A set $A$ is computable (like in Turing machines) iff its characteristic function $$\chi\_A(x) = \begin{cases}1, & x \in A\\ 0, & x \notin A\end{cases}$$ is recursive. The class of recursive functions (sometimes referred to as $\mu$-recursive functions) is the smallest class that contains all constant functions, successor function, projection, and is closed under substitution, primitive recursion and minimization.

So yes, every computable function is recursive w.r.t. to the definition above.

# Answer
> 0 votes
Can you define what it means to solve a problem "only" with recursion?

Would your definition allow an algorithm like this:

```
int foo(int n) {
    if (n==1) return 1;
    while(someCondition) {
        do something
        foo(n-1);
    }
}

```

If your definition would wllow this, then it would be easy to transform every algorithm in such a recursive form (you could do all your calculations in the outermost function call and do nothing in the recursive calls).

---
Tags: turing-machines, computability, computation-models, recursion
---


# Question
Title: How does this reduction to prove undecidability account for epsilon?
I have the following proof that the Empty String problem:
ES = {M | M accepts $\epsilon$}
is undecidable:

$f\<M,w\>$ = Construct a new machine $M\_2$ such that:
$M\_2$ = given input x erase x from the tape and run M on w:
if M accepts w $\longrightarrow$ accept
if M rejects w $\longrightarrow$ accept
if M loops on w $\longrightarrow$ loop

I see how the function only accepts when the halting problem accepts since it only accepts when M accepts/rejects (halts). However I don't see how it only accepts when M accepts $\epsilon$ too. If for example M rejects $\epsilon$ then $M\_2$ would accept since M halted on w. Wouldn't this be a flaw in the reduction? How does this reduction account for $\epsilon$?

# Answer
> 2 votes
Let $x = \langle M, w \rangle \in H$, where $H$ is the usual haltingproblem. Then $\langle M\_2 \rangle$ halts on every input, especially on $\varepsilon$ and by construction accepts every input, especially $\varepsilon$. Hence, $f(x) = \langle M\_2 \rangle \in ES$.

Now assume $x = \langle M, w \rangle \notin H$, i.e. $M$ loops on $w$. Then $M\_2$ loops on every input, especially $\varepsilon$ and thus, never accepts it. $\langle M\_2 \rangle \notin ES$.

---
Tags: turing-machines, reductions, decision-problem, mapreduce
---


# Question
Title: Single Input Single Output Sequential Circuit Explanation Required
I'm a student of Formal Methods in Software Engineering, I'm trying to study this question for two days but still haven't figured it out, I couldn't even find a similar solution or explanation, so please if anyone can explain in detail the question and it's solution I've provided in the image, it'll be a real help. One last thing, my guess is that the solution provided in the image is not correct, or maybe its my logic that isn't, so please help me with this. Thank You.

# Answer
> 1 votes
* Create a FSA that falls on the same state at the end of a 100 sequence.
* Create a second independent FSA that falls on the same state upon the end of 011 sequence.
* Now feed a zero to both FSAs at the same time and take note of the pair of states reached. Now go back and feed a 1 and take note of the pair of states reached, and so on. You will end up with a new FSA made up of pairs of states belonging to the Cartesian product of the set of states of the first and second FSA.
* The output at the transition between two pairs of states is the logical OR of the outputs of the original FSAs.

In fact, you can also build a non deterministic FSA that does the job then turn it into a FSA.

Another solution is to create a set of states representing the last one or two inputs, namely 0, 1, 00, 01, 10, 11 in addition to a start state. The transitions are obvious. 1 is emitted when transitioning from 01 to 11 or from 10 to 00. In fact state 11 can be merged with state 1 and state 00 can be merged with state 0. That leaves us with a total of 5 states that should do the job. I assume here that the outputs are emitted upon transitioning. Assuming the output is emitted upon entering a state, then states made of the last 3 inputs need to be made. Similarly, some states can be merged.

---
Tags: automata, finite-automata, formal-methods, software-engineering, sequential-circuit
---


# Question
Title: SAT solver optimizations of DPLL for unsatisfiable formulas
I am implementing a SAT solver based on DPLL algorithm, and it works fine on small formulas and larger satisfiable problems. My case split is based on a tree like structure, where every branch is tried one by one until solution for the problem is found or until every branch is tried.

So my problem now is that the above described approach does not terminate when trying to find a solution on large UN-SAT problems (so there shouldn't be a solution), therefore my program tries every possibility $2^n$, giving it a run time of years to solve UN-SAT problem with $50$+ variables (it would eventually terminate in years as I am not having any memory issues etc.).

My question is: what topics/implementations would I want to look at to speed up the tree processing or this case split process on unsatisfiable problems. Thanks.

# Answer
Conflict analysis and clause learning and non-chronological backtracking should help a lot, for both satisfiable and unsatisfiable instances. They discover large portions of the search space where no solution can reside and prune the search to avoid traversing those.

You could also try two-watched-literals unit propagation, but I'd try the others first, as I expect they'll make a bigger difference.
> 1 votes

---
Tags: algorithms, logic, satisfiability, sat-solvers
---


# Question
Title: $\lambda$-calculus, is there encoding of for or while?
In $\lambda$-calculus, we can encode arithmetic, numbers, booleans, and even compute factorials of numbers, as shown here.

Is there encoding of "for" or "while"?

# Answer
Sure! Let me show how to encode FOR using an example.

Suppose we want to translate a simple factorial FOR program

```
x := 1
for i := 1 to N do
   x := x * i

```

We rewrite it as

```
x := 1
i := 1
repeat N times
   x := x*i
   i := i+1

```

then we put all the variables we use in a tuple (a pair suffices, here)

```
(x,i) := (1,1)
repeat N times
   (x,i) := (x*i, i+1)

```

This effectively applies the function $\lambda\langle x,i \rangle. \langle x\*i , i+1 \rangle$ to the initial pair $\langle 1,1 \rangle$ for $N$ times.

Since $N$ can be represented as a Church numeral, we get

$$ N (\lambda\langle x,i \rangle. \langle x\*i , i+1 \rangle) \langle 1,1 \rangle $$

The above syntax uses a few things beyond the plain lambda calculus. Numbers and arithmetic can be made precise using Church numerals. Pairs also have their own Church encoding:

$$ \langle x,y \rangle \equiv \lambda k.kxy \qquad \lambda \langle x,y \rangle . M \equiv \lambda z. M\\{zT/x, zF/y\\} $$ where $z$ is a fresh variable, $T = \lambda ab.a$ and $F = \lambda ab.b$.

If you have more than two variables, you can generalize the above encoding to tuples, or simply represent tuples as nested pairs.

---

WHILE is best dealt with using recursion: instead of

```
while p(x,i) do
   (x,i) := f(x,i)

```

where `p` is a predicate and `f` is some (partial) function, we can use something like

```
def recFun(x,i):
   if p(x,i):
      return recFun(f(x,i))
   else:
      return (x,i)

```

In the lambda calculus, recursion is obtained using a fixed point combinator, e.g. Church's $Y$ or Turing's $\Theta$. We get something like

$$ Y (\lambda r . \lambda \langle x,i \rangle . {\sf if}\ p x i\ {\sf then }\ r(f \langle x,i \rangle)\ {\sf else}\ \langle x,i \rangle) $$

where ${\sf if}\ b\ {\sf then }\ t\ {\sf else}\ e \equiv b t e$ assuming booleans are Church encoded.

Also note that WHILE is (strictly) more powerful than FOR. Every FOR can be encoded as a WHILE, so this encoding technique can also be used for FOR.
> 11 votes

# Answer
There are encodings of loops, but they don't work exactly like the loops that you're used to, because the lambda calculus is not an imperative language. The lambda calculus has no side effects (it's a purely functional language), so the exact equivalent of a loop would be useless.

## Explicit state

An imperative program can be translated to a purely functional language by passing all state around explicitly as a variable in the program. I'll use Python syntax for imperative pseudocode; it should be mostly transparent, with the indication that `(a, b) = f(…)` means that the call to the function `f` returns a pair and `a` and `b` are assigned the first and second component of the pair respectively. Consider a loop

```
while test_condition():
    do_stuff()

```

Let's make the state explicit.

```
state = initial_state
(state, cond) = test_condition(state)
while cond:
    (state, cond) = test_condition(do_stuff(state))

```

We can translate this to a recursive call. `def loop(state):` defines a function called `loop`.

```
def loop(state):
    (state, cond) = test_condition(state)
    if cond: return loop(do_stuff(state))
    else: return state
state = loop(initial_state)

```

This only uses the following concepts, all of which can be expressed easily in the lambda calculus:

And thus we can define a `while` function for a condition $C$ (`test_condition`) and a body $B$ (`do_stuff`): $$ \mathsf{while} := \lambda C. \lambda B. \mathsf{fix} (\lambda f. \lambda s. (\lambda p. \text{BODY} (\mathsf{first}\\, p) (\mathsf{second}\\, p)) (C \\, s)) \\ \text{where BODY} = \lambda s'. \lambda c. \mathsf{if} \\, c \\, (f \\, (B \\, s')) \\, s' $$

For loops vary depending on the programming language, but they're always a special case of while loops, so they can be encoded in the same way. If the source language limits the expressiveness of for loops, there may be simpler encodings. For example, “repeat $n$ times” is simply function composition $n$ times, where the function is the state transformation that constitutes the body of the loop, and if $n$ is a Church numeral then that's simply applying $n$ itself to the loop body function.

## Adding state to the language

An alternative approach to state is to extend the lambda calculus with state manipulation primitives. If you do that, the order of evaluation becomes important. In that case, a while loop can be expressed directly with recursion. $$ \mathsf{while}\_{\text{imperative}} := \lambda C. \lambda B. \mathsf{fix} (\lambda f. \mathsf{if} \\, C \\, (B; f) \\, ()) $$
> 9 votes

---
Tags: lambda-calculus, computation-models
---


# Question
Title: Question about H-gate on entangled qubits
I have a question about the Hadamard Gate on entangled qubits. I’m very newb to quantum computing and does not have any professional knowledge in physics nor mathematics. However I’ve tried some different algorithms in IBM’s quantum experience and think I got the idea about how the qubits works in the block sphere. Because of my poor knowledge in physics I need a simple explanation and I want to understand it...

My problem:

When I do the following operation:

```
q[0]: H   ( + )   H
q[1]:          *

H = Hadamard Gate
( + ) = CNOT control
* = target

```

I get the following results when I measure q\[0\] and q\[1\] after 1000 shots:

1/4 times: 11 1/4 times: 01 1/4 times: 10 1/4 times: 00

What I don’t get is why the first qubit is measured as as a 1 (only) 1/2 times and as a 0 1/2 of the times. My theory before the measurement was that q\[0\] would always be measured as a 1 all the times since I put it in superposition \<+| and then put it back (after the second H gate and the CNOT) to be measured along the X-axis. So what have I missed?

# Answer
> 1 votes
Assuming that the initial quantum state is $\left| 00 \right\rangle$, the effect of the circuit is $$ \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \cdot \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix} \cdot \begin{bmatrix} 1\\0\\0\\0 \end{bmatrix} = \begin{bmatrix} 1/2\\1/2\\1/2\\\-1/2 \end{bmatrix}, $$ where the rows and columns are indexed by $\left|q\_0q\_1\right\rangle = \left|00\right\rangle,\left|01\right\rangle,\left|10\right\rangle,\left|11\right\rangle$. When you measure the two qubits at the end, you should get each of the four possibilities with probability $(\pm 1/2)^2 = 1/4$, which is exactly what you have observed.

If, however, you apply the CNOT gate with input roles reversed, you get $$ \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \cdot \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix} \cdot \begin{bmatrix} 1\\0\\0\\0 \end{bmatrix} = \begin{bmatrix} 1\\0\\0\\0 \end{bmatrix}, $$ so in this case you will always measure $\left|00\right\rangle$.

---
Tags: quantum-computing
---


# Question
Title: Given an oriented graph, return true if paths have a specified length
I'm having trouble solving this exercise about graphs, I hope you can help me:

*Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an integer $k$, verify in $O(|V|+|E|)$ if each path that starts from a vertex $v \in A$ and connect a vertex $u \in B$ have a length that is greater or equal than $k$.*

So if each vertex in $A$ that connect a vertex in $B$ have a length that is greater or equat to $k$, you should return $true$; otherwise, if exists at least one vertex of $A$ that connect a vertex in $B$ on a path that have a length that is less than $k$, you should return $false$.

My problem is to guarantee the linearity on the graph's dimension. My idea was to execute $|A|$ BFSs, one for each node that is contained in $A$. But, if $|A|=|V|$ i have a complexity that's squared on the graph's dimension.

Thank you very much.

New Update : I've tried to think about the Dijkstra algorithm; in that algorithm i have one source and i have to calculate the shortest path from the source and other nodes. Still it's easy if i have one source, but if i have a set of nodes, still cannot guarantee the linearity. Please, do you have more specific hint?

# Answer
> 1 votes
Let's say a vertex $v$ is at distance $t$ from the set $A$ if there exists a path of length $t$ from some element of $A$ to $v$; and there is no shorter path.

Can you think of an efficient way to compute the distance from $A$ to each individual vertex in the graph?

Perhaps you might like to modify BFS. Hint:

> Maybe you can think of some way to change the initialization, to make BFS do what you want.

---
Tags: graphs, shortest-path, graph-traversal
---


# Question
Title: I can not understand some petri net properties ( quasi-liveness and liveness )
Can anyone please help me understand the quasi-liveness and liveness properties of petri nets. Suppose that you explain that to a person with 10 years old.

For my part, i have the following definitions. \- quasi-liveness petri net: its mean that every transition in the net can be enabled at least one time for specific marketing. So may be enabled many times. -liveness petri net: its mean that every transition in the net can be rechargeable from any marketing.

Am i right ?, can you give me a simple example. Finally what is the best method to find these properties ?

# Answer
> 3 votes
Here are three examples that exhibit the properties you wondered about. The background colour of every enabled transition is green. The background colour of every non-enabled transition is white – the same background colour as the rest of the corresponding diagram.

The Petri Net and its initial marking in Figure 1 is quasi-live. It is not live because after changing from green to white once transition 1 will never change colour from green to white again.

**Figure 1 A Petri Net that is Quasi-Live**

The Petri Net and its initial marking in Figure 2 is live and quasi-live. Every transition in the net can change colours from green to white more than once.

**Figure 2 A Petri Net that is Live and Quasi-Live**

The Petr Net and its initial marking in Figure 3 is neither live nor quasi-live. Transition 1 will never change colour from green to white.

Figure 3 A Petri Net that is neither Live nor Quasi-Live

It may not be easy to imagine the colour changes; so I also created a dynamic and interactive PDF version of this reply. With the PDF version you can control the animation of each figure and see the colour changes.

# Answer
> 4 votes
To answer your first question:

An attempt to explain Petri nets in terms some 10-year olds will understand (see, for instance, Murata's well-known description):

1. A Petri net is a diagram that consists of three kinds of elements. We call them *transitions*, *places*, and *arcs*. In the example above, the transitions are green boxes and the places are white rounds. The arcs are arrows that run from places to transitions and from transitions to places. Transitions and places have names. A place may contain *tokens*. A token is usually drawn as a little dot.
2. A Petri net describes a set of circumstances in which changes can happen in certain ways. It describes exactly how the changes can happen. For each change, it describes the conditions under which it can occur, and the conditions that result from the change.
3. A *transition* describes a possible change. Its name should name that change. For example: *a customer arrives*, or: *switch the light off*, or: *the light breaks*, or: *the sun goes down*.
4. A *place* describes a possible condition. Its name should name that condition and should be of the form: *something* (for example: a person, thing, place, etc.) is *something* (a condition that that person, thing, place, etc. is in). For example: *the sun is shining*, or: *a customer is waiting*, or: *a spot is available*, or: *the light is broken*.
5. A *token* describes a particular something for which the condition holds, and to which the change applies. For instance: the sun shining, or: a customer waiting, or: a spot being available, or: the light being broken.
6. The arcs describe which conditions must hold for a change to occur, by running from exactly those places to that transition. They describe which conditions will hold as a result of the change, by running from that transition to exactly those places. In the example given above: *switch light on* is only possible if the *light is off*; after *switch light on*, the *light is on*. Etcetera.
7. As we said above, the places of a Petri net can contain tokens. In some Petri nets, like the example above, they never contain more than one token; in other examples they do contain more than one token. When a change occurs (we say: a transition fires), usually the count of tokens changes: some places get fewer tokens and other places get more. We can describe the state we are in by saying how many tokens are in each place. We call such a listing a *marking* of the Petri net. So a marking lists for each place how many tokens are in that place.

In the example above, the marking has only one token, in *light is on*. Only two transitions can fire: the upper *light breaks* and *light is off*.

If *light breaks* fires, we end up in the marking that has one token in *light is broken* and no tokens elsewhere. After that, no transition can ever fire again.

If instead, *switch light off* fires, we end up in the marking that has one token in *light is off* and no tokens elsewhere. In that marking, two transitions can fire, namely the lower *light breaks* and *switch light on*.

If *light breaks* fires, we end up in the marking that has one token in *light is broken* and no tokens elsewhere. After that, no transition can ever fire again.

If instead, *switch light on* fires, we end up in the marking that we started with.

With that out of the way, we can describe quasi-liveness and liveness:

A transition is said to be *quasi-live* if it can be fired at least once. That is, from the present marking, either it can fire directly, or by firing transitions it is possible to arrive in a marking in which it can fire directly. In other words: in the present situation, there is a way in which this change can occur, either now or in the future.

In the example above, every transition is quasi-live: as we have seen, two transitions can fire directly, while for the other two, a transition can fire such that they can then fire.

A marking is said to be quasi-live if all transitions are quasi-live for that marking. In other words: in the present situation, *all* changes can still occur, either right away or later. This is the case in the example above.

A marking is said to be *dead*, *a deadlock*, if no transitions can fire. *No* changes can ever occur. This is the case for the marking we reach after firing one of the *light breaks* transitions.

A transition is said to be *live* if it is quasi-live in every possible marking. That is to say: in *any* situation, that change can still occur, either right away or later. In the example above, no transition is live: we have found we can reach a dead marking, in which none of them can fire.

A Petri net is said to be live if all of its transitions are live. In any situation, all of the changes can still occur. Clearly, this is not the case in the example above.

We can change the example by adding new transitions: *repair light*. That would give us a live Petri net.

To answer your second question: a standard reference for how to determine liveness of Petri nets is Murata's article mentioned above. I recommend it; it is readable and the techniques it describes are readily applicable.

Deciding whether an arbitrary Petri net is live is possible, but very hard. See, for instance, this informal discussion by prof. Javier Esparza. A fairly recent article (E. Best and H. Wimmel, Structure Theory of Petri Nets in: Transactions on Petri Nets and Other Models of Concurrency VII, 2013) says:

> For liveness we know that it is at least as hard as the reachability problem. The latter is EXPSPACE-hard, and no upper complexity bounds are known at the present time.

So researchers have focused on defining limited classes of Petri nets for which properties such as liveness are easier to decide; for instance, it is co-NP-complete for *free-choice* nets.

---
Tags: automata, petri-nets
---


# Question
Title: What is the significance of the imaginary parts in the output of an Inverse Fourier Transform? Can I avoid them?
Starting with an image, I have taken its fourier transform and then modified it, and finally taken the inverse fourier transform of the modified fourier transform to get my resulting image. In my result, I get a lot of very small imaginary components in each pixel. My question is what causes these, and is there some insight into how I can play with a fourier transform in such a way that I won't get these imaginary components once I invert the transform at the end?

The reason this is an issue for me is because although I can simply zero out the imaginary components, or take the magnitude of each complex number as the pixel value and still obtain the resulting image that I desire, once I take the fourier transform of that new image, it does not yield the fourier transform that I used to generate the image previously. Because the English is getting messy, it's much easier to see in pseudocode:

```
function fft(input):
   return 2D fourier transform of input 2D array

function ifft(input):
   return 2D inverse fourier transform of input 2D array

function fix(image):
   zero out imaginary component in each pixel of input image (2D array)
   return updated image

// Suppose we have computed an input 2D matrix, and are ready to ifft it to get an image
input = /*...*/
test1 = fft(ifft(input))
test2 = fft(fix(ifft(input)))

```

While `test1` will yield back the matrix (up to floating point errors) `input` that we started with, the image generated is not a real image. If we attempt to `fix` the image, we find that `test2` significantly differs from our `input`.

What I would like to do is understand how to modify the fourier transform in such a way that I can achieve my original input after going through the process of taking the inverse fourier transform, storing that as a valid image, and then taking the fourier transform of that image.

# Answer
The Fourier Transform is the change of basis, the discrete signal from image, which is finite, gets transformed into sines. The transformation itself is prone to rounding, because in frequency domain there is no such thing as finite impulse or rectangular for that matter (see Gibbs effect), there will be some approximation.

The complex numbers represent the transformed signal, where amplitude is the length (magnitude) of the number while phase is the angle. Cutting off the imaginary part destroys the phase and changes the amplitude so image looks like a noise. There is no way to avoid Imaginary part (unless the image itself is fully even-symmetric then Im is zero).

The small components in Imaginary part cannot be avoided, extending precision will help a lot, but please keep in mind that some inputs cannot be preserved and some loss will occur. Using only magnitude and discarding the phase is equivalent to saving pixel intensities and discarding the location.

If you want to store FFT result as the valid image, the best idea is to produce two images, for Real and Imaginary part or another pair using Phase and Magnitude. Another idea is to save separate channels, which works for grayscale image but is not sn option for grayscale. This operation is very lossy, some fixed unsigned integer (for example 8bit) is converted into complex pair, both floating point, so using any standard storage option will lose crucial data. Probably to make it work the log transform would be need.
> 1 votes

---
Tags: image-processing, fourier-transform
---


title: A question about the definition of PRFs

text:
# Question
Title: A question about the definition of PRFs
Let $\mathcal{F} = \\{ f\_{s} \\}\_{s \in \\{\\, 0,1 \\,\\}^{\*}}$ be a family of computable functions, where $f\_{s} \colon \\{\\, 0,1 \\,\\}^{|s|} \rightarrow \\{\\, 0,1 \\,\\}^{|s|}$.

We define a family of functions $\mathcal{H} = \\{ h\_{s} \\}\_{s \in \\{\\, 0,1 \\,\\}^{\*}}$, where $h\_{s} \colon \\{\\, 0,1 \\,\\}^{|s|} \rightarrow \\{\\, 0,1 \\,\\}^{|s|}$ and $h\_{s}\left( \cdot \right) = f\_{s}\left( f\_{s} \left( \cdot \right) \right)$.

Let $F\_{n}$ ($H\_{n}$) be the distribution of functions $f\_{s}$ ($h\_{s}$), where $s$ is uniformly distributed over $\\{\\, 0,1 \\,\\}^{n}$. And let $R\_{n}$ denote the uniform distribution over the set of all functions from $\\{\\, 0,1 \\,\\}^{n}$ to $\\{\\, 0,1 \\,\\}^{n}$.

We know that for any PPT adversary $A$, if for all $n$, $$\left\vert \Pr\left\[ A^{F\_{n}}\left( 1^n \right) = 1 \right\] - \Pr\left\[ A^{R\_{n}}\left( 1^n \right) = 1 \right\] \right\vert \leq \epsilon (n)$$ then $\mathcal{F}$ is a family of PRFs. And if $\mathcal{F}$ is a family of PRFs, then $\mathcal{H}$ is also a family of PRFs.

How about $A$ can only can query the oracle of a function sampled only one time? In other words, if $$\left\vert \Pr\left\[ A\left( F\_{n} \right) = 1 \right\] - \Pr\left\[ A\left( R\_{n} \right) = 1 \right\] \right\vert \leq \epsilon (n)$$ holds true, can we get that $$\left\vert \Pr\left\[ A^{F\_{n}}\left( 1^n \right) = 1 \right\] - \Pr\left\[ A^{R\_{n}}\left( 1^n \right) = 1 \right\] \right\vert \leq \epsilon (n)$$

PS: The title may not clear enough, but I don't know how to make it better :(. Thanks for anyone helping me to make it better :).

# Answer
Let $F\_n$ be a random involution induced by a random perfect matching on $\\{0,1\\}^n$. For any input $x$, the distributions of $F\_n(x)$ and $R\_n(x)$ are almost identical (in fact, $F\_n(x)$ has the same distribution as $R\_n(x)$ conditioned on the event $R\_n(x) \neq x$, which occurs with probability $1-2^{-n}$), so they are statistically indistinguishable. However, $H\_n$ is the identity function, so it is easy to distinguish from a random function.

With some more work, it might be possible to extend this from one query to any fixed polynomial number of queries.
> 2 votes

---
Tags: pseudo-random-generators
---


# Question
Title: Constructing an FSA, where Ratio of number of states of FSA to its Minimal DFA Equivalent < 0.5
I need to choose a language, design a finite automaton M such that L = L(M). Construct a minimum-state DFA M′ equivalent to M in such a way that the ratio of the number of states in M to the number of states in M′ is less than 0.5.

I have zero idea as to how I should approach this. I've tried considering a few DFA's, as its the best place to start, considering that NFAs obviously have fewer states than their corresponding DFAs, but I'm not able to think of an approach to derive or contemplate a DFA with it's minimal counterpart having states \< 0.5 times number the original DFA.

# Answer
> 4 votes
What the question is really asking you is:

> How much saving can be achieved by "compressing" a DFA to its equivalent minimal DFA?

The answer is: the amount of saving which can achieved is unbounded. There are (at least) two ways to measure the saving:

1. Number of states which are eliminated.
2. Number of states in the new automaton as a fraction of the original number of states.

The number of states which are eliminated is unbounded, and the number of new states as a fraction of the number of original states can be arbitrarily close to zero.

An example is not hard to come by: pick you favorite minimal DFA, and add as many dummy states as you want. These dummy states will not be reachable from the initial state of the original DFA, so thy won't affect the language accepted by the DFA; but they will increase the number of states by an amount of your choice.

What if we disallow this example by asking all states in the DFA to be reachable? What if ask, moreover, that there be an accepting state reachable from any state? (This makes sense as stated if we're allowing the DFA to get stuck, in other words, for the transition function to be a partial function; but a similar condition can be defined for DFAs with total transition functions.) The statements above still hold true, and an example is not difficult to come up to. I challenge the readers to figure out such an example.

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


# Question
Title: Repeated or conditional evaluation to solving which values of n insertion sort beats merge sort
I'd like to solve the questions below with repeated or conditional evaluation but I don't know how.

1. Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n\*log(2,n)$ steps. For which values of $n$ does insertion sort beat merge sort?
2. What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?

Any pseudocode would help me so much. Thank you.

# Answer
> 1 votes
$$8n^2\<64n\lg n\iff \frac n{\lg n}\<64.$$

Using a grapher, $n\le588$.

---

$$100n^2\<2n\iff n\<\frac1{50}$$

There is no solution.

---
Tags: algorithms
---


# Question
Title: Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }
PDA = Pushdown Automata

Let's assume I have this language:

$L = \\{a^nb^ma^n | m,n \ge 1\\}$

Would the first approach with one node be enough - in that case it guess twice the $\lambda$. In the second approach it's deterministic, which is fine.

# Answer
Here is a solution with one stack.

1. Start inserting a's into the stack.
2. Stop inserting a's when we encounter the first b. Halt any operations with respect to the stack as long as we get b's.
3. Start popping stack contents immediately when the b's stop and a's start.
> 0 votes

---
Tags: computability
---


# Question
Title: Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise)
Exercise 1.3 from Vijay Vazirani - 'Approximation Algorithms' asks:

Consider the following factor $2$ approximation algorithm for the cardinality vertex cover problem. Find a depth first search tree in the given graph, $G$, and output the set, say S, of all the nonleaf vertices of this tree. Show that S is indeed a vertex cover for $G$ and $|S| ≤ 2$ · $OPT$. Hint: Show that $G$ has a matching of size $|S|/2$.

$EDIT$: the hint originally reads as follows: 'Show that G has a matching of size |S|'. A counterexample to this is when G is a path of length $4$ - then the DFS tree $T = D$, and a maximum matching is of size $2$. I took this to be a misprint and assumed that $|S|/2$ is the number the hint meant to refer to. Now after reading fade2black's comment, he also has a counter example in which $S$ is not a cover of $G$. After thinking about this for a while, I now cannot see for what reason $|S|$ should always be a cover of $G$. What I thought was proof of this statement (my attempt at the first part of the question below), is actually proof that $S$ is always a cover of $T$. Any ideas? Am I missing something? Is this a misprint, or is this just a poorly formulated question?

My attempt:

Showing $S$ is a vertex cover of $G$: Assume not. Then there is at least one vertex $v \in G-S$, $s.t.$ $v$ is a leaf and not adjacent to any vertex in $S$. Then either $v$ is disconnected in $G$, or $v$ is adjacent to some other leaf in $G$. If $v$ is adjacent to some other leaf in $G$, this implies that $G = K\_2$, in which case $S = \emptyset$ and selecting either of the two vertices on its own gives a vertex cover. Therefore, if $G \neq K\_2$ and $G$ is connected, $v$ must be connected to some $w \in S$.

Showing that $|S| \leq 2 \cdot OPT$: Consider a $2$-colouring of the vertices in $S$. At least one of the colours will have been used to colour at least half of the vertices in $S$. Pick that colour, and for each vertex coloured by it, match exactly one of its incident edges. It follows that $G$ admits a matching of size $|S|/2$. Let $M$ be a maximal matching in $G$. Then $|S|/2 \leq |M|$. We know that the minimum cardinality vertex cover of $G$ can be bounded from below by $|M|$, i.e. $|M| \leq OPT$. Together this gives $|S|/2 \leq |M| \leq OPT$, which implies that $|S|/2 \leq OPT \implies |S| \leq 2 \cdot OPT$.

Im pretty happy with the logic behind my solution to the second part of the exercise (showing that $|S| \leq 2 \cdot OPT$), but I'm not sure if the first part is quite there - I think the logic needs a bit of work. Any suggestions?

# Answer
> 2 votes
In this exercise, we think of the DFS tree (in fact, DFS forest) as a rooted tree (in fact, forest). We define *leaf* and *nonleaf* accordingly. In particular, the root of the tree is not a leaf vertex unless it is an isolated vertex.

In order to prove that the set of nonleaf vertices is a vertex cover, you have to notice that no edge can connect two leaves $x,y$ of the tree, since if $x$ is the vertex reached first, then $y$ will be a descendant of $x$.

# Answer
> 0 votes
I am writing it as an answer since it is too big for a comment.

My concern is the claim "*Show that S is indeed a vertex cover for $G$*". I assume the standard definition of a vertex leaf and the standard definition of a vertex cover.

Consider a cycle graph on $n$ vertices: $v\_1,v\_2,\dots, v\_n, v\_1$. This graph has a DFS tree $v\_1,\dots, v\_n$ which has only two leaf vertices $v\_1$ and $v\_n$. Then consider the set of nonleaf vertices of this tree, i.e., $\\{v\_2, \dots, v\_{n-1}\\}$. Is it a vertex cover? The edge $\langle v\_n,v\_1\rangle$ is not covered by this set.

---
Tags: graphs, combinatorics, approximation
---


# Question
Title: How to prove/disprove distribution of division over union
How can I prove distribution of division over union in relational algebra, i.e. the following:

$$(R \cup S) / X \overset{?}{=} (R / X) \cup (S / X)$$

# Answer
Ok so i figured it out. Let $L\_1$, $L\_2$ be relation sets where $L\_2$ is a subset of $L\_1$. We know $R$ and $S$ are subsets of $L\_1$ and $X$ is a subset of $L\_2$. Since we do not know whether $X$ is a subset of $R$ and $S$, we can give the following counter example:

Suppose $$\begin{align\*} L\_1 &=(1,2,3,4,5,6,7,8), \\ R &= (1,2,3,4), \\ S &= (5,6,7)\\; \text{and}\\ X &= (1,3). \end{align\*}$$ Then, $(R \cup S) / X = (2,4,5,6,7)$ whereas $R / X$ and $S / X$ are illegal.
> 0 votes

---
Tags: relational-algebra
---


# Question
Title: Why is the Marking Algorithm takes O(number of marks) ?
I am referring to the Marking algorithm defined in this article: https://arxiv.org/pdf/1602.00621.pdf

The Marking method is defined at the bottom of page 4 and has a pseudo code at the beginning of page 5.

In page 7 they claim "The runtime of the marking stage is O(B)". B being an upper bound for the number of marks of the marking algorithm.

To me It seems like the Marking algorithm should take O(|A|n), A being the positions in its input.

Can someone help me understand this?

# Answer
> 1 votes
After mailing the author, I've found the answer:

The marking algorithm can be done in $O(B)$ by making sure that every unit of time we spend produces one mark. Consider the following piece of code:

```
for i in 1..|T|
  for j in A s.t. T[i]==P[j]
    m[i-j+1]++

```

The second loop need not take $O(|A|)$, it can be implemented more efficiently by precomputing the matching positions for every character in the alphabet. For example, if $T\[i\]$ happens to be '$c$' then we precompute all the offsets $j$ in $A$ for which `P[j]=='c'`. Then every iteration of the second loop produces a mark, like this:

```
for i in 1..|T|
  for j in offsets[T[i]]
   m[i-j+1]++

```

The total number of marks is $\sum\_{a\in A} F\_a=B$ because every position $a\in A$ has $F\_a$ marks. So the run time is $O(B)$.

---
Tags: algorithms, string-matching
---


# Question
Title: Recovering species from a phylogenetic tree
*This question is based on Problem 2 from the 'Bioinformatics contest' of 2018.*

Given a *phylogenetic tree* $T=(V,E)$ of $n$ vertices, in which some leaves are assigned an integer color $c$ from $\[1,n\]$, the task is to find a coloring of the vertices $C:V\rightarrow \[1,n\]$ such that the subtree induced by each color is *convex*, i.e. there is exactly one vertex that has no parent in the induced subgraph of that color. An equivalent formulation is that the subgraphs induced by each color must be connected.

We are given that there exist a coloring meeting these constraints (there may be multiple). What is an efficient algorithm to find such a coloring?

---

*Biological interpretation*: The idea is that we're only given that some taxa (leaves in the tree) are of the same species and we do know the full ancestor tree. The assumption of convexity of a species means that each species has a common ancestor of the same species. Of course, this information isn't always sufficient to reconstruct the whole tree, but it might recover significant parts.

---

**BONUS**: So far, this is only the first case of the problem given in the contest. Observe that the above definitions remain unchanged if we replace $T$ by a DAG $D$ with a single vertex without parent (=*single source DAG*). Is there an efficient algorithm that solves this problem on general single source DAG's or edge-cactus single source DAG's?

# Answer
I present an algorithm for the tree case. The algorithm solves the problem in two 'passes' through the tree: first from leaves to root, then from the root to the leaves.

---

**Algorithm:** First, we augment our tree $T$ with the additional field $v.subcolors$ for each vertex $v$. This field should contain the set of all colors present in the subtree rooted at $v$ (with $v$ included).

We traverse the tree 'layer by layer' from leaves to the root: Our first layer consists of all leaves. The next layer is constructed by taking the set of parents from all vertices in the current layer, which we repeat until we reach the root.

Then, we fill in the field $v.subcolors$ for all vertices $v$ in our layer. This is easy to do, as we know that $w.subcolors$ is already set for all children of $v$, as those belong to the previous layer we've already visited.

Observe that some vertex $v$ must be of color $c$ if and only if it *separates* two vertices of color $c$, i.e. it lies on the (unique!) path between two vertices of color $c$. We can determine whether $v$ separates some vertices easily if we know what colors lie in the components formed by removing $v$ from the tree: if the color $c$ lies in two distinct such components, $v$ must separate some vertices in those components.

We can efficiently find the colors in the subtree of the children of $v$, as that is given by $v.subcolors$. The parent of $v$ is a bit more tricky. However, if the parent has already been colored with color $c$, $v$ can be a separator of some vertex the component of the parent only if that vertex has color $c$! Otherwise, if there were some other color $c'$, the parent of $v$ would *also* separate those vertices. But the parent has color $c$, which means that the coloring of the parent of $v$ is incorrect. This contradicts our assumption that we know the correct color of the parent (note that we have assumed a valid coloring exists!)

So, we can now color the vertices by traversing the tree from root to leaves, again layer by layer: we check at each vertex $v$ whether it separates vertices of some color (as a valid coloring exists, this is at most once color) and fill in that color. If it separates no vertices of the same color, we simply give it an unused color from $\[1,n\]$.

---

**Efficiency:** Coloring the sub-tree requires traversing the tree from bottom to top. As we need to compute with the field $v.subcolors$ at most once for every edge in the tree, this part takes $O(|E|) = O(|V|) = O(n)$ time.

For the down-traversal, we must perform a comparison again for each edge. We can check for each color and vertex adjacent to $v$ whether it occurs and see if it is a separator if it occurs twice. This takes $O(\mathrm{degree}(v)\cdot |C|)$ time if we store the color sets in a hash-table, where $|C|=n$, the number of colors. As the average degree of a tree is constant, performing this operation on all vertices takes $O(n^2)$ time.

So, in total, the algorithm runs in $O(n^2)$ time. This turned out to be fast enough for the testcases given in the contest.

This time could maybe be improved by using an efficient union algorithm to check the separator more efficiently. (Union-find doesn't seem to do the trick, as the sets aren't disjoint)
> 2 votes

# Answer
Algorithm:

1. Find the Lowest Common Ancestor of each color: this node can act as source for the color.
2. Starting from each source, paint all their descendants doing a Depth First Search (the search must stop when another LCA is visited).
3. If the root of the tree is not painted, paint it and all its unpainted descendants (via DFS) with the color of the highest LCA.

Finding the LCA of a set of nodes can be done by searching for the LCA in this way: $LCA(n\_1,n\_2,\ldots) = LCA(n\_1, LCA(n\_2, LCA(\ldots)))$.

There are many algorithms for finding the LCA of a pair of nodes. The fastest in this case would be to use some $O(n)$ preprocessing technique (Wipipedia lists some), which then allows for constant time queries (again, $O(n)$ queries tops). The complexity of this algorithm is thus $O(n)$.

In this article you can find a simpler $O(n\log n)$ approach that would suffice in the case of the Bioinformatics Contest.
> 2 votes

---
Tags: algorithms, graphs, bioinformatics
---


# Question
Title: Proving an algorithm must have the lowest time complexity for sorting in the worst case
I'm curious if anything like this has been proved, or is even possible to prove a statement like: **"Out of all sorting algorithms, this one has the lowest time complexity for the worst-case."**

Or stated more specifically, the statement could look like: **"Quicksort has the lowest time complexity for worst case of all sorting algorithms because X, Y, Z"**

# Answer
Sorting with comparisons is know to be an $\Omega(n\log n)$ problem and we know several sorting algorithms that reach that bound in the worst case (Heapsort, Mergesort).

(The justification is short: the decision tree able to distinguish among the $n!$ possible permutations of the input has a height at least $\log\_2 n!$.)

In some special cases comparison-less methods are possible and may lead to an $\Omega(n)$ bound. Worst-case optimal algorithms are also available (Histogramsort).
> 3 votes

---
Tags: time-complexity, sorting
---


title: Eigenvalue computation for large graph

text:
# Question
Title: Eigenvalue computation for large graph
Consider a large graph, minimum 1 000 vertices but it can easily go up to 50 000 vertices depending the case. The graph is the result of social relationships (followers, following, friendship) so it can be oriented but for the ease of the solution let's say it's not, so the matrix is symmetric. Moreover the matrix of adjacency is highly sparse.

I need to calculate the eigenvalues, but the major problem as I see it is that computing eigenvalues for large adjacency matrices cost a lot on time complexity due to matrices operations. If I can't efficiently compute all the eigenvalues, even a method to find the largest eigenvalue would be nice.

I've searched through the literature in vain, is there an algorithm or other approach to solve this?

# Answer
There are many methods for computing the eigenvalues of a matrix.

If you just want the largest eigenvalue, the power method is an efficient way to do that, as Yuval suggests. Typically the power method takes $O(n)$ time to find (an approximation to) the largest eigenvalue of a $n \times n$ matrix, if the matrix is sparse (it has $O(1)$ non-zero entries per row), with a constant of proportionality that depends on the matrix (and specifically on the value of $|\lambda\_1/\lambda\_2|$).

A generalization is the Lanczos algorithm, which lets you find the top $k$ eigenvalues in a sparse Hermitian matrix in $O(kn)$ time, with a constant of proportionality that depends on the matrix. Arnoldi iteration is a generalization to non-Hermitian matrices.

If you want to find all eigenvalues, there are multiple methods. The QR algorithm has $O(n^3)$ running time, though it doesn't take advantage of the sparsity of your matrix. Arnoldi iteration can apparently be used to find all eigenvalues, or the $k$ largest eigenvalues, but I don't know what its asymptotic running time is. There are apparently also software libraries that support eigenvalue computation on sparse matrices, e.g., Eigen, ARPACK, SuperLU, Spectra, OpenNL. I have no experience with them and cannot recommend one.

For more you might check Computational Science.SE, e.g., https://scicomp.stackexchange.com/questions/tagged/sparse+eigenvalues.
> 3 votes

---
Tags: graphs, time-complexity, linear-algebra, adjacency-matrix
---


title: On importance of Stockmeyer theorem

text:
# Question
Title: On importance of Stockmeyer theorem
> Theorem: (Stockmeyer, 1974) Any circuit that takes as input a formula (in the language of WS1S) with up to 616 symbols and produces as output a correct answer saying whether the formula is valid or not, requires at least $10^{123}$ gates.

Suppose we have generalized theorem: Any circuit that takes as input a formula with up to $n$ symbols and produces as output a correct answer saying whether the formula is valid or not, requires at least $10^n$ gates. Is this true that this theorem equivalent to statement that P is not equal to coNP?

# Answer
The theorem is false. There is a circuit of size $\tilde{O}(2^n)$ that solves SAT. At any rate, the relevant conjectures you would be proving using statements of this form are the Exponential time hypothesis and its variants.
> 3 votes

---
Tags: complexity-theory, circuits, co-np
---


# Question
Title: What graph theory algorithm(s) would help solve this problem?
I have a directed graph with the following properties:

1. Except for a few special progenitor nodes, every node has two parent nodes
2. Any node can have any whole number of child nodes
3. The graph is generated such that no node is a descendant of itself in the following way: I starting with a few progenitor nodes (which have no parents) then randomly select two nodes and create a "child" node with directed edges going from each parent to the child. I repeat that step an arbitrary number of times.

I'd like to find an algorithm to efficiently identify subgraphs with the following properties:

1. The subgraph consists of two "parent" nodes and some or all of their descendants
2. Except for the two "parent" nodes in the subgraph, each node has both parents also contained in the subgraph (that is, if the subgraph were separated from the rest of the graph, no node would be separated from its parents, except for the two "parent" nodes).

It's easy to find a 3-node example of this type of subgraph - just take any two nodes and one of their mutual children. However, I'd like to be able to efficiently identify larger examples of these subgraphs.

I'd really appreciate some help pointing me in the right direction. I thought that what I need might be related to finding "weakly connected components", but I haven't made much progress, and my inexperience with graph theory makes it hard to figure out what to search for. Thanks!

PS: I've provided an example depiction of one of these graphs

# Answer
> 3 votes
Given two progenitor vertices $u$ and $v$, the following "modified flood fill" builds a set $P$ of additional vertices to include:

* While a vertex $x$ exists whose parents are both in the set $\\{u, v\\} \cup P$:
    + Add $x$ to $P$.

This will halt with $\\{u, v\\} \cup P$ being the largest possible set of vertices for the given pair of starting vertices. You want the subgraph this vertex set induces: To get that, just include every original edge that links two vertices in the set.

To do this reasonably efficiently, you could maintain 3 vertex sets $V\_0, V\_1, V\_2$, where $V\_i$ contains every vertex with exactly $i$ parents in $\\{u, v\\} \cup P$. Whenever some vertex $x$ is added to $P$, all of its neighbours in $V\_0$ or $V\_1$ are promoted to the next higher set (e.g., if some neighbour $y$ was in $V\_1$, it is moved to $V\_2$). These updates can be done in constant time per neighbour by using three doubly linked lists for $V\_0, V\_1, V\_2$, as well as a length-$|V|$ array $A$ of pairs $(i, p)$: $A\[u\].i$ is the current set number (0, 1 or 2) for vertex $u$, and $A\[u\].p$ is a pointer to its linked list node. The main loop just reads from $V\_2$ until no unread vertices remain. Each vertex and edge in the graph is processed only once, so the overall time for a single starting vertex pair is $O(|V|+|E|)$.

Thanks to D.W. for catching a problem in my first algorithm.

---
Tags: algorithms, graphs
---


# Question
Title: How do you convert a regular expression to its disjunctive normal form?
A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r\_1 +r\_2 +\dots+r\_n$ for some $n ≥ 1$, where none of the regular expressions $r\_1, r\_2, \dots, r\_n$ contains the symbol $+$ (union).

For example, the regular expression $a^\*b^\* + (ab)^\* + (c(acb)^\*)^\*$ is in disjunctive normal form.

The task is to prove that every regular language can be specified by a regular expression in disjunctive normal form. Considering that every regular language by default can be represented by a regular expression, the question now seems to simplify to proving that any regular expression can be converted to or expressed in disjunctive normal form. Any idea on how that is possible?

# Answer
The proof is by structural induction. I will define an operator $T$ that takes an arbitrary regular expression, and outputs an equivalent regular expression in disjunctive normal form:

* Base cases: $T\[\epsilon\] = \epsilon$, $T\[\sigma\] = \sigma$, $T\[\emptyset\] = \emptyset$.
* If $r = s + t$, then we define $T\[r\] = T\[s\] + T\[t\]$.
* If $r = st$, by induction we know that $T\[s\] = s\_1 + \cdots + s\_n$ and $T\[t\] = t\_1 + \cdots + t\_m$, where $+$ doesn't appear in any of the $s\_i$ or $t\_j$. We define $T\[r\] = \sum\_{1 \leq i \leq n} \sum\_{1 \leq j \leq m} s\_i t\_j$.
* If $r = s^\*$, by induction we know that $T\[s\] = s\_1 + \cdots + s\_n$. We define $T\[r\] = (s\_1^\* \cdots s\_n^\*)^\*$.

It is routine to prove by structural induction that $T\[r\]$ is a regular expression in disjunctive normal form which is equivalent to $r$.
> 4 votes

---
Tags: regular-languages, regular-expressions
---


title: Go Back N ARQ Question

text:
# Question
Title: Go Back N ARQ Question
I am a computer science under graduation student, and was going through some Go Back N ARQ (Computer Networking) videos on YouTube, and got a doubt in a question, which according to me should have a different answer than what the instructor on the video is arriving at (given that no other comment in the comments section of the video raises the same doubt, I am pretty sure I have had some problem in understanding the protocol). I would be greatful for any help. The question goes as follows:

Given a connection oriented communication between two hosts that are following the Go back N protocol, with `sender's window = 3`, and assuming that every `5th` packet transmitted by the sender is lost (no acknowledgements are lost), what are the total number of transmissions required by the sender host? Assume that the packets to be sent are numbered `1-10`.

The sequence of transmissions by the sender that I am getting is (final answer = 16):

```
1,2,3; 4,5,6; 5,6,7; 8,9,10; 8,9,10; 10

```

Meanwhile, the instructor in the video gets it like this (final answer = 18):

```
1,2,3,4,5,6,7,5,6,7,8,9,7,8,9,10,9,10

```

I would appreciate if someone could point out where I am going wrong in understanding the protocol. Thanks!

# Answer
`1-2-3` is correctly sent and acknowledged so the sender's window is now over `4-5-6`.

`4` is received correctly and so it is acknowledged. This makes the window (currently over `4-5-6`) slide to `5-6-7`. However, since `5` was lost, `5` will not be acknowledged. Therefore, despite `6` being well received, `6` will not be acknowledged as well. Meanwhile the sender sends `7` because his window allows him to (it looks like you think it doesn't trigger the sender to send `7`). It is received well but the recipient doesn't acknowledge it because it's still waiting for `5` to arrive. The sender's timer goes off and therefore it sends `5-6-7` again... (etc).

If you haven't seen it already, this animation is really helpful.
> 5 votes

# Answer
the sequence would be: 1 2 3 4 5 6 7 5 6 7 8 9 7 8 9 10 9 10

first slot: 1 2 3

next : 2 3 4

next : 3 4 5

next : 4 5 6

next : 5 6 7

now 5th packet is lost. so the above whole slot would be resend according to the procedure of go back n.

next : 5 6 7

now the counting of the 5th packet will start from the last packet after which the packet was lost i.e 6

next : 6 7 8

next : 7 8 9

now. counting from the 6 which was first sent, we know that 7th packet will again be lost. so the above whole slot will be repeated again.

next : 7 8 9

next : 8 9 10

next : 9 10

now, 9th packet will again be lost and the whole slot would be sent again.

next : 9 10

next : 10

hence, in total there would be 18 tranmissions.

thank you.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: Defining computable functions on arbitrary sets
Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to exhibit a Turing machine that computes it. In the case where the function is not from strings to strings, something about this bothers me.

I will introduce the problem with a simple example. Suppose that I define a function from binary trees to binary trees, and I want to show, formally, that it's computable. To do that I would have to exhibit a Turing machine that computes it. Since binary trees are not strings, I first have to design a string representation of binary trees. For example, I could represent the tree

as `((*,*),(*))`. Having done this, I can then pass binary trees to Turing machines in string form, and get trees back in string form, no problem.

But here's my problem: the representation of binary trees as strings is itself a function (in fact a bijection) from binary trees to strings. How can I know formally that *this* function is a computable one?

On an intuitive level I have no problem seeing that it is, but on a formal level I can't exhibit a Turing machine to verify it, because then I would need a string representation of binary trees, and we quickly get into an infinite regress. For simple things like binary trees the computability of the representation is obvious, but for more complicated sets it might not be.

Can this circle be squared --- is there a formal definition of computability for functions of arbitrary countable sets that might not admit an obvious mapping to strings of symbols?

# Additional thoughts

Here is another way of explaining my question: we might choose to define a model of computation that operates inherently on trees or some other set rather than strings. Indeed, many such models of computation have been proposed, including the lambda calculus and combinator calculi (which are arguably more naturally seen as operating on trees rather than strings), the recursive functions (which operate on integers), and various cellular automata (which operate on infinite strings or two dimensional lattice configurations, rather than finite strings). It's only really historical accident that led the string-based Turing machines to become the gold standard against which other models of computation are judged.

The problem is that without being able to talk about computable mappings between these sets, it's not strictly formally possible to say whether these other models of computation are equivalent to Turing machines or not. While it usually doesn't raise any practical problems to just think of everything in terms of string representations, it seems dissatisfying that our theory of computation doesn't treat all models of computation equally, but instead privileges those whose input and output are from a particular kind of set.

So really my question is whether a theory of computation exists has been formulated that is model-agnostic, in precisely this sense of not privileging one particular kind of set for input and output. It's quite an abstract question, motivated more by a desire for formal niceness than by any practical concerns.

One suspects, for example, that the category theorists might have done some work in this direction. This is because category theory tends to talk about the properties of functions without talking much about the sets they map, so a "category of computable functions" would probably not know or care whether its underling objects were sets of strings or something else. This is an approach I would be particularly keen to read about if it exists. (I've asked another question, specifically about the category theory aspect, over at MathOverflow.)

# Answer
> 5 votes
Effective model theory studies *computable structures*. The collection of all finite trees is a two-sorted computable structure in which one sort consists of vertices (which can be identified with the natural numbers) and the other sort consists of trees. It has the following relations:

* $\operatorname{vertex}(x)$, which is true if $x$ is a vertex.
* $\operatorname{tree}(x)$, which is true if $x$ is a tree.
* $\operatorname{appears}(x,T)$, which is true if $x$ is a vertex that appears in the tree $T$.
* $\operatorname{edge}(x,y,T)$, which is true if $x,y$ are two vertices in $T$ which are connected by an edge.

(We don't really need both $\operatorname{vertex}$ and $\operatorname{tree}$, but we do need to be able to express being in the domain of the structure, i.e., either a vertex or a tree.)

Formally speaking, to complete the definition of the structure we have to specify an encoding of the domain, either as strings or as natural numbers (this is an arbitrary choice which doesn't make much difference). Under any reasonable encoding, all the relations above will be computable, and so we have a computable structure.

A *computable presentation* of this structure is an isomorphism which maps this structure to another computable structure. This mapping has to be an isomorphism of structures, but it doesn't have to be computable. A computable structure $\mathcal{A}$ is *computably categorical* if whenevever $\mathcal{A}$ is isomorphic to a computable structure $\mathcal{B}$ (by a computable presentation), then there is a *computable* isomorphism between the two structures.

Using this vocabulary, what you might be asking is whether the computable structure of finite trees is computably categorical. (There is actually more freedom in your question, since you might want to use a different relational structure.) Some simple computable structures are computably categorical (for example, the rationals with the order relation, and the natural numbers with the successor function) and some aren't (for example, the natural numbers with the order relation), see Computable structures: presentations matter by Shore.

# Answer
> 4 votes
Unfortunately, as Raphael says, the answer is no.

The formalist answer is that computability is defined for functions $f:\\{0,1\\}^\* \to \\{0,1\\}$; it's not defined for functions on other domains.

A possible motivation is that classical computability theory is concerned with what can be computed on a digital computer. A digital computer operates on bits. Thus, it's perhaps not surprising that classical computability theory is concerned with computations where the input is a binary string. We can choose to interpret that bit-string as a representation/encoding of a tree, but that interpretation is up to us (humans). Computers have no way to accept a tree directly as input; they can only accept a sequence of bits on their input.

If we want to reason about computations on trees, we define an input encoding $e:\mathcal{T} \to \\{0,1\\}^\*$ that maps a tree $T$ to a bit-string $e(T)$. Then, we feed the bit-string $e(T)$ as the input to the computer. Formally, the computer accepts the bit-string $e(T)$ as input, not $T$ itself. Once we have fixed an input encoding, this allows us to transfer results about computability on bit-strings to computability on trees.

Formally, you could define a notion of computability on trees as follows: we could say that a function $f:\mathcal{T} \to \\{0,1\\}$ is computable (with respect to the input encoding $e$) if there exists a computable function $g:\\{0,1\\}^\* \to \\{0,1\\}$ such that $f = g \circ e$. Of course, those results may depend on the input encoding. (In practice it doesn't depend on the input encoding as long as you choose a "reasonable" encoding, because in practice reasonable input encodings are fairly trivial and don't hide any non-trivial computation; or formally, if $e\_1,e\_2$ are any two "reasonable" input encodings, usually the mappings $e\_1(e\_2^{-1}(\cdot))$ and $e\_2(e\_1^{-1}(\cdot))$ are computable, and obviously so, which means that the choice of input encoding doesn't affect which functions are considered computable, as long as you choose a "reasonable" input encoding. However there's no formal definition of what counts as a "reasonable" input encoding.)

I realize this might seem highly unsatisfactory. I do sympathize. I think that's a reasonable reaction.

That said, let me share a perspective that might help you feel a little better about the situation. Computability theory is about what functionality can be computed: given a *specification* of the desired input-behavior of a computer, it lets us determine whether it's possible to find an implementation that achieves that behavior. Usually we are interested in non-trivial specifications where it's not obvious whether such a specification is even attainable.

Once you add the input encoding, we think of something external (e.g., a human) as applying the input encoding before the data is given to the computer. Then, computability theory is only concerned with what the computer can compute, not what a human can do.

The input encoding usually has nothing very interesting going on. Usually, we can easily identify a straightforward input encoding that maps from, say, trees to bit strings. It's not a situation where we have only a specification and we're not sure whether it is possible to implement it. Rather, we usually can immediately identify an implementation, and it is obvious that a human could apply it if they wanted -- so there is no question about whether the input encoding is achievable. (If there *is* a question, we choose a different input encoding until we have one that is self-evidently achievable.)

So, computability theory concerns itself with a situation where we have a specification of desired behavior and we want to know whether it is attainable. Input encodings don't fall into that situation; usually we already know they are attainable, so the core question of computability doesn't even come up. We don't need to ask whether the input encoding is achievable because we already know how to achieve it. Ultimately, computability theory is just a tool to answer questions, and any question you might have about computability on trees seems to either fall out naturally as a consequence of computability on strings, or else isn't well-posed; so there's not really any loss of generality by focusing on computability on strings.

I'm not sure if that will help you feel any better about the situation.

# Answer
> 2 votes
In addition to the other answers given you might look at higher type computability which studies certain set like things and what it means for functions to be computable between them. Domain theory gives a set theoretic answer to what functions you can compute in the lambda calculus and in things like PCF. In particular you can ask questions like what functions are computable on $(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$ or $((\mathbb{N} \to \mathbb{N}) \to \mathbb{N}) \to \mathbb{N}$

A neat fact is that if one consideres "$\to$" to refer to the *total* functions then elements of $((\mathbb{N} \to \mathbb{N}) \to \mathbb{N}) \to \mathbb{N}$ have decidable equality!

---
Tags: computability, computation-models, encoding-scheme
---


# Question
Title: Understanding Incentive Compatibility of pooled Bitcoin Mining paper
I'm trying to understand the paper *Incentive Compatibility of Bitcoin Mining Pool Reward Functions* (Schrijvers, Bonneau, Doneh and Roughgarden, in *Financial Cryptography and Data Security – FC 2016 Workshops*, BITCOIN, 2016; PDF).

In page 3 Section 2.1, they say pool operator does not know actual $\alpha\_i$ mining power of player $i$. To estimate $\alpha\_i$ depends on the reported shares and solutions.

A reward function $ R\colon H \mapsto \[0,1\]^n$ is a function from a history transcript to an allocation $ \\{a\_i\\}\_{i=0} ^ {n} $ with $ \sum\_i a\_i =1 $. I don't understand this? What allocation does the authors mean?

What I somewhat understand from next para is $ H(k) = b = (y\_1(k), \cdots, y\_i(k) ) $ where $y\_i(k)$ is no of shares reported by player $i$ in round $k$. This I am basing on $H$ contains for each miner $i$ the total no of shares $b \_i$ reported in that round. History transcript is given by a vector $b \in N^n $.

Also what do they mean when they say " We use vector notation for $b$, so $b\_1 + b\_2 $ means component wise addition of these, and $\\|b\\|\_1 = \sum\_{i=1}^n b\_i $ is the sum of components of $b$"

Could someone explain with examples or in a more concrete way ? Also any suggestions for understanding this paper would be much appreciated. Thanks.

# Answer
Let's assume $n=3$ and at round $t$, miner\_1 reported 2 shares, miner\_2 reported 3 shares, and miner\_3 reported 5 shares. And we'll further assume that in rounds from 0 to $t-1$, none of them reported any shares.

$R$ is the reward function that takes the history of the shares reported by all miners and returns a n-length vector, $a$, consisting of real numbers between 0 and 1. Where $a\_i$ corresponds to the fraction of total reward earned by miner $i$. So $ \sum\_i a\_i =1 $. $R\_i$ corresponds to the reward earned by $i^{th}$ miner. So $R$ returns $\<.2, .3, .5\>$. When $i=1$, $R\_i$ returns $.2$

$b\_i$ (normal font) is the total number of shares reported by miner $i$. And $\textbf{b}$ (bold font) is a vector of length $n$, where each element corresponds to the shares reported by each miner. So $\textbf{b} = \<2, 3, 5\>$. When $i=1$, $b\_i = 2$. And vector at round $t$, vector $\textbf{b}$ is denoted as $\textbf{b}\_t$. So $\textbf{b}\_1$ corresponds to the vector of shares reported at round 1 and $b\_1$ corresponds to the shares computed by miner $i$.

Say at round $t+1$, $\textbf{b} = \<1, 2, 7\>$. So total shares reported in round $t$ and $t+1$ is component wise sum of $\textbf{b}\_t$ and $\textbf{b}\_{t+1}$.

Hope this helps.
> 1 votes

---
Tags: algorithms, cryptography, game-theory, one-way-functions
---


# Question
Title: Which is easier for human perception: type of variable before or after its name?
In some programming languages type of variable goes before it's name. In another - name goes first and then type. Which version loads brain less and allow easier think about problem ?

# Answer
I don't *think* there is any research (with good methodology) on this. The language I'd most expect to have actually thought about this and made an empirically-based decision is the Quorum programming language. It uses a "type before variable name" approach (though it does put the *return type* of a method declaration after the parameter list). However, what I believe is the primary source for the language design decisions, An Empirical Investigation into Programming Language Syntax (available via the first author's web site), does not mention this aspect or suggest that it was studied in the research reported on in that paper. There is other research by that group and research by others that was used to design Quorum, so it's possible it *is* covered in that other research. I haven't read it all. You can try contacting one of the creators of Quorum and asking them if they made that decision based on empirical research. If you do and you get a positive response, I would highly recommend self-answering this question with a reference to the research.
> 7 votes

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


title: Mergesort recurssion tree depth...logs

text:
# Question
Title: Mergesort recurssion tree depth...logs
I think some of the log properties are flying over my head but I'm trying to understand how the depth of mergesort is...

$1 + \log\_2 n$

I understand that to get the depth, you would have to divide $n$ by $2^x$ but I don't how this leads to the above.

It's probably some simple log principal but I'm not sure.

# Answer
The merge sort algorithm creates a complete binary tree, which has depth '**d**' and at each level, a total of **n** elements. So, **2d ≈ n**, which implies **d ≈ log2 n**
> 3 votes

# Answer
I will assume that by depth, you mean the number of levels of partitioning (splitting the components into two parts) that merge sort performs.

If this is the case, the algorithm for finding the depth should **not** be "log2(n) + 1", but rather the ceiling of "log2(n)" (the ceiling function rounds numbers **up** to the nearest whole number).

This is because there are two types of inputs you can start with:

1. When "n" is a power of 2.
2. When "n" is not a power of 2.

In the first case, you can keep partitioning the input into components until you reach components of size 1. At this stage there can be no more partitioning and the number of levels of partitioning is a whole number. Thus the answer is not affected by the ceiling function.

In the second case, you can partition the input into components however you will arrive at a stage when some inputs have components of size 2 as well as components of size 1. This is represented in the logarithm by the decimal numbers when you calculate "log2(n)". Obviously you cannot take a fraction of a step, so the ceiling function rounds it up to the next whole number.

TLDR: "ceiling(log2(n))" instead of "log2(n) + 1"

Note that in this answer I do not consider the root level as a level of partitioning. If I did wish to, I would simply "+1" to the ceiling.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Match dictionary to misspelled word, corner cases
I'm trying to think of corner-cases where I can skip having to linear-search through my dictionary in my problem; For a given word **w1**, find all matches with the least editing distance from it in the dictionary D (Levenshtein distance).

The dictionary can contain 500.000 words so a linear search through it can tend to be quite costly. The tricks I've come up with so far includes;

* Check if D contains wi (distance = 0) before beginning search
* Since a lower bound for the Levenshtein distance is abs(w1.length-w2.length) I don't calculate the Levenshtein distance for two words if their length-difference is greater than the smallest Levenshtein distance I've found so far
* I re-use parts of my Wagner-Fischer-matrices if two words I've searched for after one another have letters in common
* I calculate all the words you can get using **one** operation on wi and check if any of those are in the dictionary data structure (of the 'physical' dictionary) -\> if so I return them and stop the search (since I've already checked that the word isn't in the dictionary).

Are there any more cases in where I can manage to skip searching through the whole thing? I've thought about calculating all words that you can get with a distance of two from a word, but it feels like it's too costly combinatorically..

# Answer
> 1 votes
Are we talking about a dictionary containing words of some language? Then there are many, many tricks you can use.

Your dictionary may contain 500,000 words, but people don't use that many. And they don't make arbitrary spelling mistakes, but typically only a small number. So you could have a second dictionary containing previous results. If I enter "wierd" you find "weird" after a lengthy search, but then you add "wierd" to a second dictionary.

You can look at the word and decide what is most likely the correct spelling. Like "messsage" is probably "message", without consulting your dictionary. You could map "messsege" to "m, vowel, s, vowel, g, optional vowel", and have a second dictionary for mapped words, which would tell you that your word is likely either "message" or "massage". This will work best for complicated words that nobody knows how to spell correctly.

If you know that your word was typed on a keyboard, there are errors that are more likely than others. If you know that your word was scanned by a scanner, there's a completely different set of errors, like "wam" might really be "warn" (nobody would make that mistake typing on their keyboard). For keyboard entry, the user's fingers might have moved to a different position on the keyboard. Like "leubpard" is "keyboard" with the right hand moved one position to the right. That's a case where simple algorithms fail completely.

Split your dictionary into the 5,000 most common and the 495,000 less common words. Most likely you find a good match within the first 5,000 and can remove most items in the large list that cannot be better.

# Answer
> 0 votes
If you only need to find a single match: if you find a match at edit distance one, you can immediately stop without searching for any other matches -- that's the best one you'll ever find.

Why? The edit distance is a non-negative integer, so the only smaller edit distance possible is zero. However, you already checked that the word is not in the dictionary (that was your first bullet point), so edit distance is zero. That means that as soon as you find a distance-one match, you know you'll never find anything better.

---

Another trick: Suppose the best match you have found so far has edit distance $k$, and now you are comparing word w to word d. Then it suffices to use an "early-out" version of the edit distance computation: if the edit distance between w and d is $\ge k$, we don't care what its precise value is, as this is not a better match. This can be used to speed up the computation a little bit: rather than computing the entire matrix, we only compute the elements that are most $k$ away from the diagonal.

If you want all matches of the minimal edit distance, change $\ge k$ to $\>k$.

---

As mentioned in my comment to your prior question, there's *lots* written on spelling correction and this problem. There are many data structures, algorithms, and tricks documented in the literature and online. I suggest you spend some quality time doing some research and familiarizing yourself with them.

# Answer
> 0 votes
Best is pointless if best is terrible
If the distance is 20% + of the word then it is not a legitimate match

In addition to match length threshold also match letters
Say your threshold is 20% then also need 80% common letters

You would need to modify the algorithm as it does not come to an answer until the end but a form that gives up when a threshold cannot be obtained

---
Tags: optimization, strings, dictionaries, program-optimization
---


title: What is a "Master-Reduction"?

text:
# Question
Title: What is a "Master-Reduction"?
I keep stumbling upon this term in my lecture notes tutorials and assignments, but I have no clue what it means, google doesnt give me anything usable *at all*.

Here is an example how this term is used (material in german, but self explanatory really)

So my question is: is this a regional dialect or some important technique that I have missed ?

# Answer
> 3 votes
When proving that a problem is NP-hard, we usually reduce another problem, already known to be NP-hard, to out problem. This process must start somewhere - there must be a first problem which is proven to be NP-hard. For this first problem, say SAT, we need to show that *every* problem in NP can be reduced to SAT. This is the *master reduction*, which reduces an arbitrary problem in NP to SAT. Following that, we use reductions that reduce a *single* problem to the problem at hand.

The name *master reduction* is perhaps common in Germany, but I have never heard of it. In any case it's just an informal name. Just like the *fundamental theorem of algebra* is some theorem that somebody at some point decided to call that way, so *master reduction* is just a term that somebody invented for some reason. I have tried to explain the significance of the term above, but in reality there is no higher significance to the term beyond the particular object it refers to.

# Answer
> 0 votes
The way I understood it is with a master-reduction we dont know how a language looks like, so we take all languages from a set and reduce them onto something else.

Say we want to show that a problem is PSPACE-complete.

We take any language $L\in PSPACE$ and reduce them onto our problem, since we often can easily show that a problem is contained in $PSPACE$ and we've shown in the last step that any language $L\in PSPACE$ can be reduced onto our problem we have shown that our problem is $PSPACE$-complete.

Edits and corrections are welcome.

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


# Question
Title: If $f(n)$ is $O(g(n))$ is it also $O(g(n-d))$?
When trying to prove that a recurrence $g(n)$ satisfies $g(n) = O(f(n))$, we sometimes are not able to find a valid $C$ to show the upper bound, so we try to prove it is $O(f(n-d))$ for some constant $d$ instead.

If we are able to prove that $g(n) = O(f(n-d)$, does this mean that it is also $O(f(n))$? If so, does this go the other way too? That is, if $g(n)=O(f(n-d))$ for some $d$, then $g(n) = O(f(n))$ as well?

edit 1: Here a valid $C$ means, $C$ such that $f(n) \<= C\*g(n)$ for all $n \> n0$ for some $n0$

# Answer
> 6 votes
The answer to your first question (whether $f(n) = O(g(n))$ implies $f(n) = O(g(n-d))$) depends on the function $g$: indeed, what you want holds iff $g(n) = O(g(n-d))$. This is a relation that holds for many functions, for example polynomials and exponentials, but not for the function $g(n) = 2^{2^n}$.

As for your second question, if $f$ is monotone (increasing) then $f(n-d) \leq f(n)$, and in particular $f(n-d) = O(f(n))$. The same holds if $f(n) = \Theta(h(n))$ for some monotone $h$. For example, if $f$ is a degree $a$ polynomial then $f = \Theta(n^a)$, and so $f(n-d) = O(f(n))$, since $n^a$ is monotone.

# Answer
> 4 votes
It doesn't imply this if $f(n)$ and $g(n)$ are functions with wide swings, like $f(n) = 1$ if $n$ is even and $n$ if $n$ is odd, $g(n) = 1$ if $n$ is even and $n^2$ if $n$ is odd. Clearly $f(n) = O (g(n))$, because you compare large values of $f$ with large values of $g$, and small values of $f$ with small values of $g$.

But if $d$ is any odd number, and $n$ is odd, then $f(n) = n$ and $g(n-d) = 1$.

Another case is that even when $f$ and $g$ are monotonic, both might grow so fast that $g(n-d)$ becomes arbitrarily small compared to $g(n)$. Take for example $f(n) = g(n) = 2^{2^n}$.

---
Tags: asymptotics
---


# Question
Title: If A is mapping reducible to B and A is recognizable, then is B recognizable too?
I learned the proof for the theorem:
If A $\leq\_m$ B and B is recognizable, then A is recognizable
and was provided with the theorem:
If A $\leq\_m$ B and A is unrecognizable, then B is unrecognizable

So does this work both ways? i.e. does this also hold?

If A $\leq\_m$ B and A is recognizable, then B is recognizable
If A $\leq\_m$ B and B is unrecognizable, then A is unrecognizable

# Answer
> 3 votes
**Answer for Corrected Question**

Short answer, no.

You can think of reductions as "making problems harder" (somewhat inline with using $\leq$ as the base symbol for reductions of).

In this case we only have two levels of "hardness", a problem/language is either recognizable ("easy") or unrecognizable ("hard") (but this obviously extends to other degrees of computability and complexity).

So if $A \leq B$, and $B$ is "easy", $A$ must be "easy" too (because it's "less than" $B$). Contrapositively, if $A \leq B$ and $A$ is "hard, then $B$ must also be "hard" (because it's "greater than" $A$).

Using this intuition, it may be a bit easier to see why the latter two are wrong:

* If $A \leq B$ and $A$ is "easy", this doesn't tell us much about $B$ (it could be "easy" or "hard").
* Similarly, if $B$ is "hard", it doesn't tell us much about $A$.

Note that as with the first pair, the second are really the same statement, just logically inverted.

**Old Answer, Just Here for Posterity**

I think you may have misread something. The second (provided) theorem is not correct, it should be if $A \leq\_{m} B$ and $A$ is unrecognizable, then $B$ is *unrecognizable*.

This is just the contrapositive of the first statement.

Following from this, the final two are mistaken.

# Answer
> 1 votes
The second is a corollary of the first.

**Using logic**

This is the easy and short answer. Assume the first theorem has been proved. That is, $B$ is recognizable (statement $S\_B$) implies $A$ is recognizable (statement $S\_A$).

In logic algebra, you write this as

$S\_B \Rightarrow S\_A$

Now these are valid:

* $S\_B$ is true and $S\_A$ is true
* $S\_B$ is false and $S\_A$ is true
* $S\_B$ is false and $S\_A$ is false

However this

* $S\_B$ is true and $S\_A$ is false **is invalid**.

Rewriting our algebraic notation back to English answers all your questions:

* If $B$ is recognizable, then $A$ is recognizable
* If $B$ is not recognizable, then $A$ may or may not be recognizable
* IF $A$ is not recognizable, then $B$ must not be recognizable.

This is usually all *implied* by the book. That's why it's a corollary. But we can explicitly invoke reductions to reach the same conclusions.

**Bonus: Using reductions**

A mapping reduction implies a function $f:A\mapsto{}B$ such that

* if $x\in{}A$, then $f(x)\in{}B$
* if $x\notin{}A$, then $f(x)\notin{}B$

> If $B$ is recognizable, then so is $A$

So if $B$ is recognizable, then using $f(·)$ you can devise a Turing Machine that halts for every $f(x)\in{}B$ as well as for every $x\in A$. This proves your first statement.

> If $A$ is unrecognizable, then neither is $B$

Let us continuing assuming that $B$ is recognizable. And let us now assume that $A$ isn't. But wait, we just proved that this can't happen. We are in contradiction!

Conclusion: if you can prove that $A$ us unrecognizable, then it is impossible for $B$ to be recognizable.

Now, for the other two, it depends on whether $B\leq\_mA$ is also true. If it is true, then the same theorem applies the way back. That's boring, so let us assume this is not true.

> If $A$ is recognizable, what about $B$?

If all you have is a mapping from $A$ to $B$, then there are strings $y\in{}B$ which you can't find with $f$. So knowing that $A$ is recognizable does not help you with $B$. You may list all strings in $A$, but that still leaves a subset of $B$ for which you can't say anything.

> If $B$ is unrecognizable, what about $A$?

On the other hand, if you know that $B$ has strings that cannot be recognized, that says nothing about $A$, because all strings in $A$ might map to the portions of $B$ that *are* recognizable. So even though $B$ is unrecognizable, it still might help you recognize $A$.

---
Tags: turing-machines, reductions
---


# Question
Title: What are definite languages? How do you formally define them?
I have a question in my homework that deals with the concept of a definite language. The question defines a definite language as follows -

"A language L is definite if there is some k(\> 0) such that for any string w, whether w ∈ L depends on the last k symbols of w." I'm supposed to do the following -

a) Rewrite this definition formally

b) Prove that every definite language is accepted by a finite automaton

c) Give an example of two definite languages L1 and L2 such that L1.L2 is not definite.

I'm breaking my head over the definition given in the question. In-depth google searches lead me to a few google books and this is what I came across -

1. Theory of Automata, Arto Salomaa :

Definite languages are completely characterized by the final subwords of a given length k of a string. The behaviour of definite automata depends exclusively on the latest k input letters for some k. Thus, the behaviour is independent of inputs which have occurred at sufficiently remote past moments.

2. Role of Theory in Computer Science: (edited by Konstantinidis Stavros, Moreira Nelma, Reis Rogerio)

Whether or not a word belongs to a given definite language can be determined by inspecting the last k symbols, where k is a constant only depending on the language. In particular, two words whose length exceed k having the same suffix either both belong to the language or both do not.

More precisely, a language L ⊆ Σ\* is said to be definite if and only if L = E ∪ Σ\*Η, for some finite languages E,H ⊆ Σ\*.

3. Theory of Formal Languages with Applications by Dan Simocivi, Richard L Tenney:

Τhis alternative definition was given by Perles, Rabin and Shamir.

A language L over the alphabet A is weakly k-definite if x ε L holds for a word x with |x| ≥ k if and only if the suffix of length k of x belongs to the language L.

For k ε Ν and k ≥ 1, a language L is k-definite if L is weakly k-definite, but it is not (k-1)-definite. A language is definite if it is k-definite for some k ε Ν.

Even after reading all this, I am not able to understand anything regarding the concept of a definite language. How can you precisely define a language to be definite when you don't know what the dependency on the last k symbols of ω is? Shouldn't the definition "depends on the last k symbols" be more clear? What can you quantify as a dependency on the last k symbols, to decide whether ω will belong to L? It doesn't make sense to me. Could you help me in getting a better, clearer, simpler understanding of this? Could you please give some examples, while explaining the concept?

# Answer
> 1 votes
> A language L is definite if there is some k(\> 0) such that for any string w, whether w ∈ L depends on the last k symbols of w.

There is of course room for interpretation here. Assuming they mean "\[it\] *only* depends on the last $k$ symbols of $w$", here's a slightly more precise rephrasing:

> A language L is definite if there is some $k$ so that all words that share the same $k$-suffix are either in or not in the language.

Try to work from here.

# Answer
> 0 votes
Okay so this is what I managed to understand. As @rici mentioned, I was definitely (no pun intended) overthinking this concept.

Using @Raphael's suggested definition -

> A language L is definite if there is some k so that all words that share the same k-suffix are either in or not in the language.

With some thinking, I came up with an easy example of a language whose membership criteria is based on a condition on the last k symbols of its string, such as -

> $$L = \\{ \text{x000} \mid \text{x ∈ Σ$^\*$} \\}, where \ Σ=\\{0,1\\} $$

The dependency here is - the last 3 symbols (i.e k=3 in this case), should be 000. Hence, all strings that share the same 3-suffix (000 in this case), are in the language.

Αll those that share any other 3-suffix from Σ$^3$ apart from 000,

$i.e$, from Σ$^3$ - {000} = {001,100,101,111,010,110,011}, are not in L. Τhis concurs to the said definition. Generalizing this example, we arrive at the following -

> $$ \textit{A language L is definite, if for some k \> 0, wu ∈ L ⇔ u ∈ L } \forall \textit{ w ∈ } \Sigma^\* \textit{ and u ∈ } \Sigma^k. $$

Therefore, L can be defined as -

> $$ L = \\{\ { wu ∈ L \mid u ∈ L\ } \forall \textit{ w ∈ } \Sigma^\* \textit{and u ∈ } \Sigma^k \\}$$

To prove that definite languages are regular, we need to prove that there are finitely many equivalence classes using the Myhill-Nerode theorem. If Σ is finite, of course, definite languages are obviously regular.

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


# Question
Title: Filling a string with wildcards with minimum cost
You are given a string with wildcards, e.g. X\***Y\*Z. Your goal is to print an input string filling all the wildcards in the given string.

You are allowed to write data to the string in blocks of fixed size: character-by-character, you can write contiguous blocks of identical characters of length 2, 3 ... N: X, XX, XXX, etc. For example:

> Block: XX, apply to the 2 position in X\***Y\*Z =\> X\*XXY\*Z

It is allowed to overwrite same characters:

> Block: XX, apply to the 0 position in X\***Y\*Z =\> XX\**Y\*Z

When you choose a size of block you would like to use, let's say S, "preparation" costs occurs: S\*L, where L - some input constant. Let's say, you picked the size 2 (cost is 2\*L), then you are allowed to write XX, YY, and ZZ to the given string. When you write a block of data to the given string, writing cost occurs - some input constant C that is independent of the block size. When you choose some block length, e.g. 2, you have to fill all blanks using block\_size = 2, you are not allowed to decrease or increase it in the middle of writing. For example, if you write the first piece of data to the given string as XX, later you are allowed to use YY and ZZ only. The same with other sizes.

Your task is to identify the minimum possible cost to fill all blanks considering costs of writing data and preparing a block.

Let's consider the example above in details. We are given a string X\***Y\*Z, L = 20, C = 10. For each option, there are a plenty of variants how to fill blanks.

1) We can fill all blanks with a block of size 1 using any characters from {X, Y, Z}. Thus, total cost is 1\*20 (prepare a block of size 1) + 4\*10 (fill 4 wildcards) = 60. Possible results, there are plenty of them:

> XYXZYXZ, XXXYYZZ...

2) We can use block size = 2. For example, overwrite X\* with XX, \** with XX, Y\* with YY, the total cost is 2\*20 (prepare the block of size 2) + 3\*10 (perform 3 writing operations to fill all blanks), the total cost is 70. Example:

> Solution 1
>
> Init: X\***Y\*Z
>
> step1: write XX at 0 =\> XX\**Y\*Z
>
> step2: write XX at 1 =\> XXX\*Y\*Z
>
> step3: write YY at 3 =\> XXXYY\*Z
>
> step4: write ZZ at 4 =\> XXXXYYZ

My current approach is, basically, straightforward brute-force - start with block\_size = 1, iterate it up to N, each time try to fill all the wildcards. If current block overwrites existing data, try changing symbol type accordingly (If a block consists of X, try using Y). If it's not possible, try another symbol type/block size.

Is there any better way?

# Answer
I think I've found a solution (thanks, Yuval Filmus and D.W.!). It consists of 2 major steps:

1) Generate a valid string at minimal steps. You start traversing a string from left to right, moving by 1 character each time. I do this recursively. At each recursion level, you iterate a substring in a range \[current\_pos, block\_size\] and continue recursion from each character. By doing this you are exploring possibilities to print, let's say, 3 characters and to continue *from any of them without any costs*. During recursion, you explore all input characters: X, Y, Z, so each time you generate 3 branches. When you hit an end of a string, corresponding **recursion depth equals to a number of used blocks**.

2) Searching for an optimal block\_size. Using binary search over a block's length to find the optimal block size could be tempting, but it does not work in general. The reason is that depending on costs of block's preparation/usage, cost function could be non-monotonic. Thus, it looks like you have to use linear search.
> 1 votes

---
Tags: algorithms, optimization, strings, discrete-mathematics
---


# Question
Title: Can two different complexity classes be equal relative to an oracle? Example request
Is there a known example of two complexity classes, $A$ and $B$, such that:

1. $A \neq B$;
2. there is an oracle $O$ for which $A^O = B^O$?

I strongly believe that there are such examples, as otherwise $P = PSPACE$ (note that $P^{PSPACE} = PSPACE^{PSPACE}$), but I was looking for an example of this.

# Answer
> 11 votes
Let $\mathsf{C}$ be a complexity class of your choice, let $\mathsf{O}$ be an oracle of your choice, and define $\mathsf{D} = \mathsf{C}^\mathsf{O}$. Then $\mathsf{C}^\mathsf{O} = \mathsf{D}^\mathsf{O}$, but it could happen that $\mathsf{C} \neq \mathsf{D}$. For example, you can take $\mathsf{C} = \mathsf{P}$ and $\mathsf{O} = \mathsf{HALT}$, the halting problem.

This might seem like cheating, but it's exactly the same answer as the one by Willard Zhan.

# Answer
> 8 votes
See Ryan Williams' answer here. An easy example is that $\mathsf{AC^0}\neq \mathsf{AC^0\[2\]}$, but they are equal relative to a parity oracle.

---
Tags: complexity-theory, reference-request, relativization
---