# Question
Title: Simple interepretation problem regarding Polynomial Hierarchy?
So $NP$ stands for problems where we have small verifiable witnesses for $YES$ instances and $coNP$ for small verifiable witnesses for $NO$ instances. How does this work for

1. $P^{NP}$
2. $NP^{NP}$
3. $coNP^{NP}$
4. and so on?

# Answer
There is a logical interpretation of the various levels of the polynomial hierarchy, which extends the witness characterization of $\mathsf{NP}$ and $\mathsf{coNP}$.

A language $L$ is in $\Sigma\_k^P$ if there is a polytime predicate $f$ and a polynomial $\ell$ such that $$ x \in L \Leftrightarrow \exists |y\_1| \le \ell(|x|) \\; \forall |y\_2| \le \ell(|x|) \\; \cdots Q |y\_k| \le \ell(|x|) \\; f(x,y\_1,\ldots,y\_k). $$ Here:

* $\exists |y| \le \ell(|x|)$ means that there exists a number $y$ whose length is at most $\ell(|x|)$ such that ...
* $\forall |y| \le \ell(|x|)$ mean that for all $y$ whose length is at most $\ell(|x|)$, the following holds ...
* $Q$ is $\exists$ if $k$ is odd and $\forall$ if $k$ is even.

Similarly, $L$ is in $\Pi\_k^P$ if it can be written in a similar way, only starting with $\forall$.

As an example, $\mathsf{NP}^{\mathsf{NP}}$ is $\Sigma\_2^P$, and consists of all languages such that $$ x \in L \Leftrightarrow \exists |y\_1| \leq \ell(|x|) \\; \forall |y\_2| \leq \ell(|x|) \\; f(x,y\_1,\ldots,y\_k). $$ As another example, $\mathsf{coNP}^{\mathsf{NP}}$ is $\Pi\_2^P$.

Your third example is $\mathsf{P}^{\mathsf{NP}}$, which is $\Delta\_2^P$. I'm not sure what is the logical characterization.
> 8 votes

# Answer
To say $\mathsf{NP}$ contains problems with "small verifiable witnesses" is conceptually inaccurate at best. The witnesses are only polynomially bounded because we want the verifier to be efficient (i.e., run in polynomial time). In such a setting, only a polynomially long prefix of any witness can be relevant, hence why we insist on polynomially long witnesses. Also, "small" potentially means constant or logarithmic; those are not used, of course, because they can be brute-forced by polynomial-time algorithms (and only give us problems in $\mathsf{P}$).

The way the proof system notion of $\mathsf{NP}$ generalizes to yield the polynomial hierarchy is much like the logical point of view that Yuval Filmus describes in his answer. Let me introduce the less technical view behind it.

We consider two-party games which are based on QBFs. An instance (or the "board" if you care to imagine it as a board game like chess or checkers) of such a game is a formula $\varphi(x\_1, y\_1, \ldots, x\_m, y\_m)$, and the two players, say $A$ and $B$, take turns choosing values for $x\_i$ and $y\_i$, respectively. Each such choice constitutes a *move*. When no more values are left, the formula (i.e., the game's final position) is evaluated; $A$ wins if it is true, and $B$ wins if it is false.

This game models existential and universal quantifiers in the following way: If the formula is a true QBF, then $A$ (which plays the role of existential quantifiers) will always have a winning strategy and be able to choose a series of $x\_1, \ldots, x\_m$ which cause $\varphi$ to be true regardless of the values $y\_1, \ldots, y\_m$ picked by $B$ (which plays the role of universal quantifiers). The "yes" instances are those in which the QBF is true, that is, $A$ always has a winning strategy, regardless of how $B$ plays.

$\Sigma\_i$ and $\Pi\_i$ then correspond to games which last for $i$ moves and in which $A$ and $B$, respectively, get to go first. Actually, you even get $\textsf{PSPACE}$ and the $\textsf{PH} \subseteq \textsf{PSPACE}$ inclusion as a bonus since it corresponds to the class of games which go on for an arbitrary (though predetermined) number of moves.

Note also that $\Sigma\_1 = \mathsf{NP}$ and $\Pi\_1 = \mathsf{coNP}$ are rather degenerate cases of these games because $B$ and $A$, respectively, do not get the chance to move at all! For example, for the "yes" instances of $\Pi\_1 = \mathsf{coNP}$, $A$ gets to win simply by doing nothing (since a "yes" instance is a tautology and is true regardless of what $B$ chooses).

There is also a more generalized version of the above which is based on generic games (and not QBFs specifically). You can find it, for instance, in section 5.4 "PSPACE and Games" of Goldreich's "Computational Complexity: A Conceptual Perspective" (here is a free link to the draft version; see p. 174 as well as pp. 118–121).
> 1 votes

# Answer
$\mathsf{P}^{\mathsf{NP}}$ is the closure of $\mathsf{NP}$ under polynomial time Turing reductions (=Cook reductions). Therefore, it is closed under Cook reductions, so that we have $\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{P}^{\mathsf{NP}}}$. In fact, for any oracle $\mathsf{A}$, we define $\mathsf{P}^{\mathsf{A}}$ as the closure of $\mathsf{A}$ under Cook reductions, and we always have $\mathsf{P}^{\mathsf{A}}=\mathsf{P}^{\mathsf{P}^{\mathsf{A}}}$ and $\mathsf{NP}^{\mathsf{A}}=\mathsf{NP}^{\mathsf{P}^{\mathsf{A}}}$. Also $\mathsf{coNP}^{\mathsf{A}}=\mathsf{coNP}^{\mathsf{P}^{\mathsf{A}}}$ and $\mathsf{P}^{\mathsf{NP}}=\mathsf{P}^{\mathsf{coNP}}$. But Cook reductions feel slightly unnatural for decision problems.

Note that $\mathsf{P}$ is a function class in disguide, and that $\mathsf{P}^{\mathsf{NP}}$ too is a function class in disguise. Let us write $\mathsf{PF}$ for the class of polynomial time computable partial functions, i.e. the function class corresponding to $\mathsf{P}$, and $\mathsf{PF}^{\mathsf{NP}}$ for the function class corresponding to $\mathsf{P}^{\mathsf{NP}}$. Including the partial functions allows to use established notation (used in A taxonomy of complexity classes of functions by A. Selman, 1994) that avoids the name clash with the unrelated class $\mathsf{FP}$.

Cook reduction feel more natural for function classes. You probably encountered a Cook reduction (and implicitly also the class $\mathsf{PF}^{\mathsf{NP}}$) at the point where your text book or professor explained why it is OK to only look at decision problems. Typically, something like an algorithm (from $\mathsf{PF}^{\mathsf{NP}}$) to compute the lexicographically last satisfying assignment of a given SAT instance is described. One first asks the oracle whether there is any satisfying assignment at all, and then determines the values of the (binary) variables $x\_k$ by successively asking the oracle whether there is a satisfying assignment where $x\_1,\dots,x\_{k-1}$ are set to the already determined values, and $x\_k$ is set to $1$. If yes, then one sets $x\_k$ to $1$, otherwise one sets $x\_k$ to $0$. (Note that this is a partial function, since the function is undefined in case there is no satisfying assignment.)

---

Let me try to say some words about Yuval Filmus remark:

> Your third example is $\mathsf{P}^{\mathsf{NP}}$, which is $\Delta\_2^P$. I'm not sure what is the logical characterization.

There are two difficulties to overcome: (1) the characterization of a function class has a different feel than the logical characterization of a decision class, and (2) at least for $\mathsf{P}^{\mathsf{A}}$ we have to model the *deterministic* character of the queries to the oracle $\mathsf{A}$.

If we look at the class $\mathsf{UPF}$ of partial functions corresponding to the class $\mathsf{UP}$ of decision problems first, then we can ignore (2) for a moment: A partial function $pf$ is in $\mathsf{UPF}^{\Sigma\_k^P}$ if there is a polytime partial function $p$, a polytime predicate $f$ and a polynomial $\ell$ such that $pf(x)=p(x,z)$ where $$\exists\_{\leq 1} |z|\le \ell(|x|)p(x,z)\neq\bot\land\exists |y\_1| \le \ell(|x|) \\; \forall |y\_2| \le \ell(|x|) \\; \cdots Q |y\_k| \le \ell(|x|) \\; f(x,y\_1,\ldots,y\_k,z). $$ Here:

* $\exists |y| \le \ell(|x|)$ means that there exists a number $y$ whose length is at most $\ell(|x|)$ such that ...
* $\forall |y| \le \ell(|x|)$ mean that for all $y$ whose length is at most $\ell(|x|)$, the following holds ...
* $Q$ is $\exists$ if $k$ is odd and $\forall$ if $k$ is even.

One could try to overcome (2) by introducing the operators $\operatorname{BIT}(z,i):=z\[i\]$ and $\operatorname{TRUNC}(z,i):=z\left|\_{\[1,i)}\right.$. But it would still get ugly, and one can argue whether this would really constitute a logical characterization.
> 1 votes

---
Tags: complexity-theory, np
---


# Question
Title: Efficient serialization/deserialization of huffman tree
I have implemented huffman encoding in the form

```
struct node
{
    node * left;
    node * right;
    double freq; // the frequency
    string letter;
    string binary_code; // the variable length code
};

```

that works fine, eg:

```
Data: electric eels
Compressed: -σ» //doesnt render in this text editor sorry
Decompressed: electric eelss
Ratio: 38%

```

But I have no idea how to efficiently encode the tree itself (needed for the decompression) to send over socket, and then decode it.

Can someone help me with some c code/pseudocode style explanation?

Any help appreciated.

# Answer
The usual approach is to build Canonical Huffman code from the frequencies and use it to encode the data.

Canonical Huffman code can be encoded in a pretty compact way, as was described in the ZIP APPNOTE.TXT file, look for words Shannon-Fano and Huffman.

You can find C code in any deflate/inflate implementation or Huff0.
> 2 votes

---
Tags: huffman-coding
---


# Question
Title: how to solve simultaneous equation with O(n)
Does someone know how to solve the below?

Assume that the array $A$ is already sorted. And show an $O(n)$-time algorithm that determines whether or not there exist indices $i,j,k$ such that

$A\[i\] + 4A\[j\] = A\[i\] + 5A\[k\] = 0$.

I came up with an algorithm that uses two double for-loop for each i, j and i,k. But the complexity will be $O(n^2)$..

# Answer
As per a comment of Albert Hendriks, we need to find $i, j, k$ such that $-A\[i\] = 4A\[j\] = 5A\[k\]$.

We can actually do this in a single linear pass. We sweep $i$ from the left, such that $-A\[i\]$ can only get smaller. We sweep $j, k$ from the right for each possible $i$. But when the left hand side can only get smaller, we don't need to check any $j$ or $k$ again that are bigger than our current $j, k$ since $A$ is sorted, thus our $j, k$ can only ever decrease giving $O(n)$ instead of $O(n^2)$.

In Python:

```
i = 0
j = k = len(A) - 1

while i < len(A):
   while j >= 0 and -A[i] < 4*A[j]:
       j -= 1

   while k >= 0 and -A[i] < 5*A[k]:
       k -= 1

   if -A[i] == 4*A[j] == 5*A[k]:
       return (i, j, k)

   i += 1

return None

```
> 2 votes

---
Tags: algorithms, complexity-theory, data-structures
---


# Question
Title: Designing solution to critical section problem with two semaphores vs single semaphore
I came across following problem:

> Let two processes P1 and P2 are there:
>
> ```
> +-----------------------+-----------------------+
> | P1                    | P2                    |
> | while(1)              | while(1)              |
> | {                     | {                     |
> |    //s1               |    //s3               |
> |    //s2               |    //s4               |
> |    //critical section |    //critical section |
> |    signal(mutex1);    |    signal(mutex1);    |
> |    signal(mutex2);    |    signal(mutex2);    |
> | }                     | }                     |
> +-----------------------+-----------------------+
>
> ```
>
> Lets mutex1 and mutex2 both are initialized to 1. So in order to avoid deadlock s1, s2, s3 and s4 (respectively) will be replaced by
> (A) wait(mutex2), wait(mutex1), wait(mutex1), wait(mutex2)
> (B) wait(mutex1), wait(mutex2), wait(mutex2), wait(mutex1)
> (C) wait(mutex1), wait(mutex2), wait(mutex2), wait(mutex2)
> (D) wait(mutex1), wait(mutex2), wait(mutex1), wait(mutex2)

**Doubt**

Given solution is D, which I understood why. But I am guessing whether having two semaphores `mutex1` and `mutex2` serve any special purpose in above code? Does below single semaphore based programs achieve same as what is achieved by above code?

```
+-----------------------+-----------------------+
| P1                    | P2                    |
| while(1)              | while(1)              |
| {                     | {                     |
|    wait(mutex1);      |    wait(mutex1);      |
|    //critical section |    //critical section |
|    signal(mutex1);    |    signal(mutex1);    |
| }                     | }                     |
+-----------------------+-----------------------+

```

# Answer
If only one semaphore is used to control the access to the critical section, it is not possible for deadlock to happen. That is why two semaphores are used in the problem statement since the problem is designed to, I assume, showcase deadlock.

A single-semaphore-based program can protect the critical section from concurrent access as well, as demonstrated by your program that uses a single semaphore.

However, some critical sections do require two or more semaphores to protect. Here is an example. There are only one fork and one knife. Each of the two diners must obtain both of them before entering the dining section. So there should one semaphore for the fork and another one for the knife. If the waiting operations of these two semaphores are not arranged in the same order for both diners, deadlock could happen. Note that one semaphore is not enough to deal with this situation correctly.
> 1 votes

---
Tags: operating-systems, concurrency, deadlocks, semaphore
---


# Question
Title: Explain auto continue passing style transformations
Recently I saw 3 cps transformation rules, but no explanations were given.

expressions: $e :=x\left|e e^{\prime}\right| \lambda x \cdot e$

rules: $$ \begin{array}{l}{\[\[x\]\]=\lambda \kappa \cdot \kappa x} \\ {\[\[\lambda x \cdot M\]\]=\lambda \kappa \cdot \kappa(\lambda x \cdot\[\[M\]\])} \\ {\[\[M N\]\]=\lambda \kappa \cdot\[\[M\]\](\lambda m \cdot\[\[N\]\]\](\lambda n \cdot(m n) \kappa)}\end{array} $$

When transforming `fib`, `fib n = ...` is transformed into `fib n k = ...`, but if we use the second rule, the first param of the transformed function will be `k` which differs

```
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fib_cps 0 k = k 1
fib_cps 1 k = k 1
fib_cps n k = fib_cps (n - 1) (\x -> fib_cps (n - 2) (\y -> k (x + y)))

```

Could someone please explain it for me?

About the 3rd rule, why we need to transform both fn and arg when transforming function application, and why it's like this?

# Answer
> 2 votes
The code you posted takes a few shortcuts. The mismatch with the rules of the CPS transform comes form your code being in Haskell, which features integers (`0,1,2`), arithmetics (`+,-`), definitions by cases, and recursion, while the CPS transform only covers the pure lambda calculus, without all the bells and whistles that come with a "usual" programming language.

Anyway the idea of a CPS function is that you never return the result of the function in a direct way. Rather, you pass that result to a *continuation function*, usually named `k`, which is an additional parameter to the function. Often, it is convenient to take `k` as the last parameter -- this is only a convention, though, and we could choose otherwise.

For instance, the constant-zero function becomes

```
zero n = 0

zero_cps n k = k 0

```

Squaring:

```
square n = n*n

square_cps n k = k (n*n)

```

Now, in the last line I cheated a bit, since there I am using `*` as the regular multiplication function, instead of using a CPS variant of multiplication. Your `fib_cps` code does the same for `+` and `-`, which are not translated into CPS. Let's continue with this.

Now, what if we want to CPS transform this composition?

```
f n = square (square n)

f_cps n k = ???

```

Intuitively, in `f_cps` we want to call `square_cps`, take its result, and pass that to another `square_cps`. But we can't do that directly, since `square_cps` does not return its result, it passes it to the continuation. So, we need to write something like

```
f_cps n k = square_cps n (\m -> ...???...)

```

where `m` is the "result" of `square_cps`, hence `m=n*n`. What do we do with `m`? We want to square it again.

```
f_cps n k = square_cps n (\m -> square_cps m (\o -> ???))

```

here `o` will be the square of the square of `n`, hence `n*n*n*n`. That is the final result, so we can pass it to `k`, which expects the result of `f`.

```
f_cps n k = square_cps n (\m -> square_cps m (\o -> k o))

```

So, in CPS style, we use this "idiom":

```
function_cps arg1 arg2 ... arg2 (\x -> ...)

```

meaning "call `function` with the `arg`s, let `x` be the result, and then proceed with `...`".

Code like `f1 (f2 (f3 (f4 n)))` becomes

```
f4 n  (\x4 ->
f3 x4 (\x3 ->
f2 x3 (\x2 ->
f1 x2 (\x1 ->
... use x1 here ...))))

```

(If you happen to be familiar with monads in Haskell, you'll see that this is very similar to a monadic `do` block. This is not a coincidence since CPS is strictly related to the `Cont` monad.)

In your `fib_cps` code, we need to do

```
fib (n-1) + fib (n-2)

```

This is transformed into a program which evaluates `fib (n-1)` first (let `x` be its result), then `fib (n-2)` second (let `y` be its result), and finally returns `x+y`. In code

```
fib (n-1) (\x ->
fib (n-2) (\y ->
k (x+y)))

```

where the last line combines the results and passes their sum to `k`, the continuation of the call `fib_cps n k`.

You might have noticed that we needed to fix an evaluation order: first `fib (n-1)`, then `fib (n-2)`. This order was not present in the original code. Indeed, to transform some code to CPS, we need to be more explicit about what we want to evaluate first.

In your CPS rules, application $MN$ is transformed into

$$ \[\[M\]\](\lambda m.\ \[\[N\]\](\lambda n.\ \ldots) $$

which forces $M$ to be evaluated first, then $N$, giving an evaluation order, similarly to what happened above.

Further, the CPS term above always evaluates $N$. This is done according to the call-by-value (CBV) semantics, where function arguments are always evaluated. So, the CBV CPS transform matches such semantics, which is used by languages like Ocaml.

Note that Haskell, instead, uses a call-by-name (CBN) semantics instead, where e.g. `zero (non terminating expression)` returns `0` immediately without evaluating its argument. If we wanted to use CPS completely preserving Haskell's semantics, we should use another form of CPS called the CBN CPS transform, which is subtly different.

In your posted `fib_cps` code, CBV CPS is used, even in Haskell, since

1. `+` always evaluates its arguments
2. we are not using a CPS version of `+`
3. CBV CPS is arguably a bit simpler to understand

I hope this does not sound too confusing. Continuations are quite tricky to understand.

---
Tags: compilers, lambda-calculus, continuations
---


# Question
Title: Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists?
Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, in some sense. However, is this an interesting question worth worrying about? Are there practical situations, where there is some benefit in reducing a more complicated language to a context free language?

# Answer
No. By Greibach's theorem, it is undecidable whether a CSG generates a context-free language.
> 1 votes

---
Tags: formal-languages, context-free, context-sensitive
---


# Question
Title: Complexity of K-Colorful Coloring Problem for a Hypergraph
I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem let me know. I think it will be NP-Complete

Let H = (V, E) be a hypergraph, and let ϕ be a coloring of H. A hyperedge e ∈ E is said to be k-colorful with respect to ϕ if there exist k vertices in e that are colored distinctively under ϕ. The coloring ϕ is called k-colorful if every hyperedge e ∈ E is min{|e|, k}-colorful. Let $c\_H (k)$ denote the least integer $L$ such that H admits a k-colorful coloring with $L$ colors.

The reference for the problem is E.Horev, R.Krakovski, and S.Smorodinsky, “Conflict-free color-ing made stronger,” in Scandinavian Workshop on Algorithm Theory,pp. 105–117, Springer, 2010.

# Answer
> 1 votes
A *strong k-coloring* of a hypergraph assigns distinct colors to every member of a hyperedge and uses $k$ colors. When the hypergraph is $k$-uniform, this problem is equivalent to the problem you describe. Further, this problem is NPC as shown by Colbourn, Jungnickel and Rosa \[1\].

You can also prove yourself that this problem is NPC by a straightforward reduction from chromatic number. Essentially, you can add enough vertices around every edge and make them into cliques and you can make the reduction work.

---

\[1\] Colbourn, Charles J., Dieter Jungnickel, and Alexander Rosa. "The strong chromatic number of partial triple systems." Discrete applied mathematics 20.1 (1988): 31-38.

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


title: Decidable Program Equivalence

text:
# Question
Title: Decidable Program Equivalence
Determining whether two programs always return same output for same input is undecidable (easily reduced to the halting problem). My question is, is there a complexity class in which this problem is decidable for machines on that class?

Seems like it must be below PTIME, as Datalog is P-Complete and equivalence of Datalog programs is undecidable.

# Answer
> 1 votes
Given a Turing machine $M$, we can construct another Turing machine $T$, which on input $1^n$ simulates $M$ for $\log n$ steps, and returns whether $M$ halted within these steps. The new Turing machine runs in linear time, and is equivalent to the constant time Turing machine which always returns "No" iff $M$ doesn't halt. Therefore program equivalence is undecidable even for linear time Turing machines.

# Answer
> 1 votes
Reversal Bounded Counter Automata have decidable equivalence. They're a fascinating class, because augmenting them in any obvious way makes one of their main properties (equivalence, emptiness, etc.) undecidable. Oscar Ibarra's work explored their properties extensively: http://www.lsv.ens-cachan.fr/~demri/Ibarra78.pdf

If I recall correctly, visibly pushdown Automata also have decidable equivalence, though I'm as familiar with that class.

---
Tags: complexity-theory, computability
---


title: Simple Hamiltonian cycle reduction

text:
# Question
Title: Simple Hamiltonian cycle reduction
> HAMPATH
>
> * **Input:** An undirected graph $G$ and 2 nodes $s, t$
> * **Question:** Does G contain a Hamiltonian path from $s$ to $t$?

> HAMCYCLE
>
> * **Input:** A undirected graph $G$ and a nodes $s$
> * **Question:** Does $G$ contain a Hamiltonian cycle starting at $s$?

I wish to show HAMCYCLE is NP-hard. I'll show this by doing $HAMPATH \leq\_p HAMCYCLE$ since HAMPATH is known to be NP-complete.

---

add edge from t to s

if theres a hampath then the reduction shows there a hamcycle

if theres a hamcycle then clearly theres a hampath

---

Above is my entire attempt. I was wondering if I could call on $t$ in my reduction since its not used as a input in HAMCYCLE?

# Answer
Instead of cutting corners and jumping right in to a reduction, I believe you would profit from actually stepping back and clarifying the logical basis of your argument.

Given an instance $(G, s, t)$ of HAMPATH, your reduction produces an instance $(G', s')$ of HAMCYCLE, as you have described. To prove your reduction works, you need to show: $$(G, s, t) \in \textsf{HAMPATH} \iff (G', s') \in \textsf{HAMCYCLE}$$ for every instance $(G, s, t)$ of HAMPATH, where $(G', s')$ is uniquely determined as a function of $(G, s, t)$ (the function in case being your reduction).

To prove this equivalence, you first fix an arbitrary instance $(G, s, t)$ of HAMPATH (which may be a "yes" or a "no" instance). $(G', s')$ is then uniquely determined by $(G, s, t)$. Then, you either prove the two sides of the equivalence (as you have done) or show that, if $(G, s, t)$ is a "yes" instance, then $(G', s')$ is a "yes" instance and, if $(G, s, t)$ is a "no" instance, then $(G', s')$ is a "no" instance. Although usually the latter is preferred, either is fine; you can reference all of $G$, $s$, $t$, $G'$, and $s'$ in both cases since they are all fixed.

The problem with your argument is that you obtain a cycle $(s, \dots, s)$ and then (correctly) reason there is a node $t'$ right before $s$ which makes it a Hamiltonian cycle (and gives you a Hamiltonian path from $s$ to $t'$). However, because $t$ is fixed, *there is no guarantee that $t' = t$*. You still need to consider the case $t' \neq t$ and show this gives you a Hamiltonian path from $s$ to $t$ even if you delete the edge $(t, s)$ (since this yields $G$ from $G'$).

Unfortunately, you will not be able to. Consider, for instance, the case where $G$ is a cycle $(s, t, v, s)$. Then both $G$ and $G'$ obviously have a Hamiltonian cycle which starts and ends at $s$, but there is no Hamiltonian path from $s$ to $t$ in $G$; the only way to reach $t$ from $s$ (by a path) is the single edge $(s, t)$, which fails to visit the vertex $v$.

You will have to modify your reduction. Hint: Try to find a way of forcing $G$ to not have a Hamiltonian cycle in the first place (and note this implies $t' = t$ above).
> 1 votes

---
Tags: np-complete, polynomial-time
---


title: Selecting the right partition in NAUTY

text:
# Question
Title: Selecting the right partition in NAUTY
Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take *some* cell of the current partition and attempt to further split the partition on more cells. What I found is that depending on the order of which you select cells during refinement, you can get different equitable partitions (at least up to the permutation of cells in the equitable partition). I guess this corresponds to the quote from Practical Graph Isomorphism II:

`It is well known that for every colouring π there is a coarsest equitable colouring π' such that π' < π, and that π' is unique up to the order of its cells.`

An example of this would be Example 7.7 (page 257), where selecting `{1,3,7}` instead of `{2,4,5,6}` will result in a permuted equitable partition

And more importantly these 2 equitable partitions can give 2 different certificates, so it is important to select the right order on the cells to get minimal among possible equitable partitions.

So my question is how does nauty ensure that during refinement it will find the “right” equitable partition and not lose the equitable partition that would potentially lead to the minimal certificate? In order words, among all (*a*) coarsest partitions how does it make sure to select *the* coarsest partition (because it selects just one equitable partition)?

# Answer
> 2 votes
After the correspondence with the creators of nauty, the answer lies in the fact that the cell is selected *deterministically* so any isomorphic graph will have the same refinement. It's actually one of the ways to reduce the total number of permutations, because it does not need to check all possible discrete partitions. And also it means that nauty does not necessarily give the certificate minimal among *all* possible discrete partitions, but rather minimal among some subset of them.

---
Tags: graphs, combinatorics, graph-isomorphism
---


# Question
Title: time efficient key value store for fast lookup
Let's state a collection of key/values.

Key is an unsigned integer (0 - 2^32-1). Hense there are comparable. Value is few bytes fixed size.

There are 4M items in the collection. Keys are **not** evenly spread in the key space i.e there is **no** way to predict hole size between two consecutive keys.

This collection is created once and never modify after that, even if not prohibited.

The aim is to lookup a value by its key. But if key is not found then the previous one (as in integer natural order) must be returned.

I'm looking for a data-structure that can be mmap on disk which would be reasonably space efficient but most importantly very time efficient for the lookup function.

There is no known pattern on how the keys are queried.

# Answer
> 3 votes
Make a table with 2^22 entries to lookup the highest 22 bits of the key. Each entry is responsible for one value on average (but may contain up to 1024).

Entry #i in the table, which is responsible for 0 to 1024 values with keys from 1024i to 1024i + 1023, contains the following: 1. The number of keys in that range. 2. If there are 0 keys, the value of the next lower available key. If there is 1 key, the lower 10 bit of the key in that range, and its value. If there are two or more keys, an index j into a second table.

In the second table, we store the lower 10 bit of the key, plus the value, for every key where there are two or more keys in the range from 1024i to 1024i + 1023. For values in the second table, we use binary search.

# Answer
> 3 votes
Since the data structure is only created once, you can simply use an array ordered by the key. Each element in the array contains the key-value pair. Sorting the array is `O(n*log(n))`, which will be fast for 4e6 items and only needs to be done once. You can then use binary search (which is `O(log2(n)` or ~22) on the array to find the key. If not found, simply return the prior element in the array.

This will be very fast and will fit even more easily in RAM because there are no pointers. It also has the advantage of being extremely simple and easy to write. If the data needs to be persisted, you just write the array to disk, use mmap if you want, etc.

# Answer
> 2 votes
The minimum possible size for such any such data structure is $\log\_2{ 2^{32} \choose 4\times 10^6} \approx 4.6\times10^7$ bits, or around 5.5MB.

An array of 4 million 32-bit numbers is only 15.25MB. So even relatively space-inefficient data structures should fit comfortably in RAM.

Any rank/select dictionary will work. Briefly, given a set $S$ of values, we can define the operations as:

$$\hbox{rank}(x) = \left| \\{ y \in S\ : y \< x\\} \right|$$ $$\hbox{select}(i) = \min \\{ x : \hbox{rank}(x) = i \\}$$

Intuitively, $\hbox{rank}(x)$ is the number of elements in the set less than x, and $\hbox{select}(i)$ is the ith smallest element in S.

As an example of a simple implementation, if you store the set as a sorted array of integers, then select is just an array lookup, and rank can be implemented with binary search.

Given those two queries, the value that you're looking for is $\hbox{select}(\hbox{rank}(x) - 1)$. However, it should be possible to take pretty much any rank/select data structure (e.g. these ones) and implement this query directly.

You may also want to consider some variant of a van Emde Boas tree. But to be honest, a B-tree (with careful implementation of the leaf nodes) might do the job.

# Answer
> 0 votes
If you have only 2^32 numbers, just make a lookup table on disk. If the number of value bytes (=n) is low enough, then just copy the values for the non existent keys from the last valid one. Otherwise introduce another indirection where you link from that lookup table to our list of 4M values.

You can calculate the access point for the value exactly: key * n Bytes. Lookup speed is O(1) for existing and non existing keys.

Disk consumption is 2^32 * n Bytes for value.

---
Tags: data-structures, dictionaries, storage
---


# Question
Title: Finding path with specific length in weighted graph
Given a weighted, cyclic, directed graph and two nodes I am looking for a connecting path which total weight comes as near as possible to a specific value which is greater than the shortest path. Example in a real world scenario: Find a route from Washington D.C. to New York City which is 400 miles long, despite the shortest path is ~230 miles. All my considerations so far failed for one of the following reasons:

* Most routing algorithms like Dijkstra are not working in this case because there is nothing to minimize or maximize (the divergence of given weight to path weight should be minimized, but you need the finished path to calculate it)
* DFS and BFS can be used to find a path with a specific number of hops (edges), but it doesn't consider weighted edges

EDIT: Cycles are forbidden to avoid the simple solution shortest path + cycles until distance is reached. The algorithm doesn't have to find the optimal solution, a route with length in a given threshold is acceptable.

# Answer
Your problem is NP-complete by a reduction from Hamiltonian $st$-path, even with unweighted arcs. Thus, you should not expect a polynomial-time algorithm. I'll sketch a reduction below.

Let $G$ be an instance of Hamiltonian $st$-path with all $m$ arcs having weight 1. Let $G'$ be a graph obtained from $G$ by adding a long directed path of length $C$ starting from $t$ ending at (say) $t'$. Now, if there's an Hamiltonian path from $s$ to $t$, there is also a path from $s$ to $t'$ of length $m$ plus $C$. On the other hand, if there's a path of length $m+C$ from $s$ to $t'$ in $G'$, you can chop off the long path from $t$ to $t'$ to obtain a Hamiltonian $st$-path in $G$.
> 2 votes

---
Tags: graphs, routing
---


# Question
Title: Terminology: Difference between decision variables, features and attributes in this paper?
Are they using the words "feature", "attribute", and "decision variable" interchangeably in this paper about an optimization method for clustering (and if so, does that go against the general use of the terms)? I've been a bit confused especially about what they really mean when they say "decision variable" since I don't see how their use of it differs from feature, but I can't find any info on google suggesting that they would mean the same thing. I don't have any formal data science education either.

Some quotes:

* "Mutation is a probabilistic operator that randomly modifies a **decision variable** of a candidate solution."
* "Suppose \[...\] POPi(s) is the sth **decision variable** of POPi (i.e. C r t, t = 1,2,…, d and r = 1,2,…, q)."
* "\[...\] max(h i(SIV)), min(h i(SIV)) are the upper and lower bounds for each **decision variable** \[...\]"
* "A SIV is a **feature** of the solution and can be imagined like a gene in GA."

# Answer
Feature and attribute have both the same meaning.

Decision variable is the variable which is used to make a split in a decision tree in tree based algorithms, i.e. the variable on which the decision is made.
> 1 votes

---
Tags: terminology, features
---


# Question
Title: How to compute number of possible paths in directed Traveling Salesman problem?
If we have directed modification of TSP, so that some routes are possible in one direction, given directed graph, could you compute number of possible tours?

What if we have supercomputer, does it make dTSP more feasible?

edit:The number of different Hamiltonian paths in undirected graph is (n−1)!/2 in fully directed version it is (n−1)!, exact number could be computed from adjacency matrix

yes but if i delete city or two from connection like this example will not be fully and this is my case:

1 to 2,3

2 to 3

3 to 1,2,4,5

4 to 2,5,1

5 to 1

so i convert dTSP to simple graph my problem is to know how many paths can i create by my edited dTSP graph so if i have

1 to 2,3

2 to 1,3

3 to 1,2

i will have number 3!= 6 paths but if i edit it to be like that

1 to 2,3

2 to 3

3 to 1

i will have 3 paths only

i found that if one city is delete from connections can cut paths maybe by double as i try and error with small numbers of cities so i want to know if i possibly can calculate number of paths that created by this given connections

# Answer
> 0 votes
The way you have written your question makes it very difficult to understand, but let me try to answer one of your points as simply as I can.

Using a "super computer" (however you might define that) will not help us to make significant progress on the travelling salesman problem. The reason is that the time taken to solve a travelling salesman problem increases *exponentially* with the number of cities.

So suppose we can solve problems with up to 50 cities in a reasonable time on an "ordinary" computer (I have made this number up as an illustration). But let's also suppose that the running time of our most efficient algorithm is $O(2^n)$ \- in other words, every time we add a city the time needed to find a solution doubles.

If we had a super computer that was a thousand times faster than an ordinary computer then it could solve problems with $60$ cities in the same time as an ordinary computer took for $50$ cities. This is because adding $10$ cities increases the problem difficulty by a factor of $2^{10} \approx 1000$.

So the super computer gives us a small improvement. But to solve problems with $100$ cities in a reasonable time we would need a computer that was a million million ($10^{12}$) times faster again.

# Answer
> 0 votes
What you're calling dTSP is no easier than ordinary TSP. You can simulate a two-way road between two cities by just having a one-way road in each direction. That means that being able to solve TSP with one-way roads means you can also solve TSP with two-way roads.

Supercomputers aren't really relevant because, with current TSP techniques, doubling the power of your computer only lets you deal with one more city in the same amount of time. So if your laptop can solve, say, 50 cities, then a computer that's 1024 times as powerful will only be able to solve 60.

# Answer
> 0 votes
The number of different Hamiltonian paths in undirected graph is $\frac{(n-1)!}{2}$ in fully directed version it is $(n-1)!$, exact number could be computed from adjacency matrix, but it is futile, according to definition:
The direction of cycle is irrelevant, both are exactly one tour, the equation reflects that, by discarding tours computed twice in bidirectional version.
So computing number of cycles is pointless, there are always $(n-1)!$ cycles in your graph.

To calculate number of paths: assume $K$ equal to $N$, and use matrix exponentation from adjacency matrix to obtain all results, keep in mind that some paths might be shorter, so there is no possible full tour. This solution counts cycles multiple times, but it is a good upper bound, efficiently computed.

For exact solution, you have to use backtracking and simply traverse them (it is unclear to me how you define path).

---
Tags: traveling-salesman
---


# Question
Title: Which languages, decided by a turing machine are decidable?
How do I decide if a language is decidable and/or semi-decidable?

I have theses languages:

a) { \< M \> | L(M) ⊆ 0\*}

b) { \< M \> | L(M) contains at least one word of even length}

c) { \< M \> | L(M) is semi-decidable}

d) { \< M \> | L(M) is decidable}

My problem is, that I don’t quite now how to interpret this notation. I know that \<M\> is the code of a turing-machine and L(M) is the language decided by the turing machine.

But I’m not quite sure if I understand “language decided by a turing machine” correctly.

Does is mean the following? I run the turing machine M and “collect” all possible words accepted by the turing machine. The collection of these words is the language?

Also: if L(M) means this is the language DECIDED by a turing machine, doesn’t this imply decidability? How can L(M) be semi-decidable if it is supposed to be the language decided by the TM?

I guess there’s a major flaw in my thoughts, but which is it?

For a) and b) I would think that they are not decidable because of the sentence of Rice: There must exist TMs which decide on a language that is element of 0\* and those that don’t. Hence the problem is not trival and it is also a functional property of the TM. Same for b.

How do I figure out if these languages a) and b) are semi-decidable? I could construct a TM that excepts all words of the form 0\* (and no other words), hence I would say that a is semi-decidable. But then I think, I could just as well construct a TM which rejects all words not of form 0\*. And that would mean that this is decidable. But that contradicts my interpretation of the sentence of Rice.

b is more difficult (in my mind at least), because the check if L(M) contains at least one word of even length I would have to check all words of L(M) and since L(M) might be infinite this may not be possible. So it would not be decidable. But it would be semi-decidable, because if I construct a TM to decide over L(M) and I run over a word with even length, I could accept it.

I know there are many errors in my argumentation (but don’t know which these are). This topic is very new to me. I’m thankful about hints on how to solve these kind of decidablity questions. The most examples I found online are about deciding whether M, not L(M) is decidable: { | M does this or that}.

# Answer
> 2 votes
Nice question.

## Notations and terms

$M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs.

$L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere.

Whether a language is decidable or a language is decided by a TM is an entirely different although closely related concept. Let me quote the definition in the book *introduction to the theory of computation* by Michael Sipser. You could take a look at its definition at Wikipedia as well.

> We prefer Turing machines that halt on all inputs; such machines never loop. These machines are called **deciders** because they always make a decision to accept or reject. A decider that recognizes some language also is said to **decide** that language.
>
> DEFINITION 3.6. Call a language **Turing-decidable** or simply **decidable** if some Turing machine decides it.

Note that if $M$ is a decider, then $M$ decides $L(M)$. If it is said that a Turing machine $N$ decides some language $A$, then $N$ must be a decider and $A=L(N)$.

## Application of Rice's theorem

Here is the Rice's theorem.

> Let $P$ be any nontrivial property of the language of a Turing machine. Then whether a given Turing machine’s language has property P is undecidable.
>
> In more formal terms, let $P$ be a language consisting of Turing machine descriptions where $P$ fulfills two conditions. First, $P$ is nontrivial—-it contains some, but not all, TM descriptions. Second, $P$ is a property of the TM's language—-whenever $L(M\_1) = L(M\_2)$, we have $\langle M\_1\rangle \in P$ iff $\langle M\_2\rangle \in P$. Here, $M\_1$ and $M\_2$ are any TMs. Then $P$ is an undecidable language.

a) $P=\\{\langle M \rangle\mid L(M)\subseteq 0^\*\\}$.

* WLOG, let 1 be an input alphabet symbol other than 0. $P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\\{0\\}$ but $P$ does not contain the description of a Turing machine whose language is $\\{1\\}$.
* $P$ is a property of the TM's language—-whenever $L(M\_1) = L(M\_2)$, we have $L(M\_1)\subseteq 0^\*$ iff $L(M\_2)\subseteq 0^\*$

By Rice's theorem, $P$ is undecidable.

b) $P=\\{\langle M \rangle\mid L(M)\text{ contains at least one word of even length}\\}$.

* $P$ is nontrivial since $P$ contains the description of a Turing machine whose language is $\\{00\\}$ but $P$ does not contain the description of a Turing machine whose language is $\\{0\\}$.
* $P$ is a property of the TM's language—-whenever $L(M\_1) = L(M\_2)$, we have $L(M\_1)$ contains at least one word of even length iff $L(M\_2)$ contains at least one word of even length.

By Rice's theorem, $P$ is undecidable.

c) By the definition of semi-decidable, a.k.a Turing-recognizable, $L(M)$ is semi-decidable for any $M$. Hence $\\{ \langle M \rangle \mid L(M)$$\text{ is semi-decidable}\\}$ contains all TM descriptions, which is a decidable language.

d) $P=\\{\langle M \rangle\mid L(M)\text{ is decidable}\\}$.

* Let $R=L(D)$ be a decidable language. For example, we can take $R=\\{0\\}$ and $D$ is a Turing machine that accepts 0 and rejects all other inputs. $\langle D\rangle\in P$. Let $H=L(N)$ be a semi-decidable but not decidable language. For example, we can take $H$ to be the language of the halting problem. Then $\langle N\rangle\not\in P$. Hence $P$ is nontrivial.
* $P$ is a property of the TM's language—-whenever $L(M\_1) = L(M\_2)$, we have $L(M\_1)$ is decidable iff $L(M\_2)$ is decidable.

By Rice's theorem, $P$ is undecidable.

<sub> For case a), if we restrict the input alphabets of all Turing machines to be the unary set $\\{0\\}$, then, of course, for every $M$, $L(M)\subseteq 0^\*$. Then $\\{ \langle M \rangle \mid\text{0 is the only tape alphabet symbol and } L(M) \subseteq 0^\*\\}$ contains all TM descriptions. It is decidable. </sub>

---
Tags: turing-machines, undecidability, decision-problem, semi-decidability
---


# Question
Title: How can the VC-dimension of Turing machine be finite?
The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all Turing Machines with $n$ states is $\Theta(n \log n)$.

However, suppose that we take the set of all such Turing machines, for $n$ sufficiently large so that the universal Turing machine is a member of $\mathcal{H}$. The result states that there exists a set $C$ (wlog, $C \subset \\{0,1\\}^\*$) of size, say, $n^2$, such that $\mathcal{H}$ cannot shatter. To my understanding, it means that there exists a function $f : C \rightarrow \\{0,1\\}$ ("labeling"), such that for every $h \in \mathcal{H}$, it holds that $h \neq f$. Since the elements of $\mathcal{H}$ are Turing machines, I say that "$h$ computes $f$" when the machine $h$ implements $f$.

But $C$ is finite hence $f$ is clearly computable, thus there is some Turing machine $M\_C$ which computes it, therefore $M\_C$ can be simulated by the universal Turing machine, which is in $\mathcal{H}$, and this is a contradiction (since we assumed $\forall h \in \mathcal{H}, f \neq h$ ). Where is the problem with this argument?

# Answer
> 3 votes
First, let me correct your definition of VC dimension: it is the largest size of a set which *can* be shattered.

If the VC dimension is $d$, then this means that for every set $C$ of size larger than $d$ there exists a function $f\colon C \to \\{0,1\\}$ which is not compatible with *any* function computed by an $n$-state Turing machine.

You are attempting to refute the claim that the VC dimension is $\Theta(n\log n)$ by showing that for any set $C$ of size $n^2$ there exists a single function $f\colon C \to \\{0,1\\}$ which is compatible with some function computed by an $n$-state Turing machine. However, what you need to do in order to refute the claim is to give a *single* set $C$ of size $n^2$ (say) such that *all* functions $f\colon C \to \\{0,1\\}$ are compatible with some function computed by an $n$-state Turing machine. Note the different quantifiers: you considered *all* $C$ and *one* $f$, but in fact you should consider a *single* $C$ but *all* $f$.

Finally, suppose that $M$ is a universal Turing machine having $n$ states. This doesn't mean that $M$ can compute arbitrary functions – in fact, $M$ computes a single function. What it does mean is that for any Turing machine $T$, $M(\langle T \rangle, x) = T(x)$. That is, if $M$ is given as input the pair $(\langle T \rangle, x)$ (where $\langle T \rangle$ is the encoding of $T$), then $M$ evaluates $T$ on $x$. This is different than what you claim, since the Turing machine being simulated is part of the input, that is, part of the set $C$.

In fact, in order to show that the collection of $n$-state Turing machines shatter a set $C$, you need to exhibit $2^{|C|}$ different Turing machines. Considering just a single universal Turing machine cannot possibly work.

Since there are only $O(n)^{O(n)}$ many different Turing machines having $n$ states (assuming the alphabet is fixed), this implies that the class of $n$-state Turing machines cannot shatter any set of size larger than $\log\[O(n)^{O(n)}\] = O(n\log n)$. This is how you get the upper bound on the VC dimension. The lower bound looks more challenging.

---
Tags: turing-machines, computability, learning-theory, vc-dimension
---


title: On the robustness of BQP class

text:
# Question
Title: On the robustness of BQP class
Typically the notion of quantum Turing machine is introduced with its transition function.

$$ \delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\\{L,R,0\\}} $$

Where $\mathbb{C}'\subseteq\mathbb{C}$ is a computable subset of $\mathbb{C}.$ This sort of definition basically gives any 1-qubit unitary gates "for free," you only need one step to perform any such unitary transform.

We knew that there's Solovay Kitaev theorem saying that any single qubit transformation could be approximated by a finite set of gates, but sometimes it still require more than $\Omega(1)$ gates to do this (grow with the precision). So it's natural to ask whether there exist an "efficient" approximation, so that when we're using just regular gates, the complexity would be roughly the same. (e.g. with only some polynomial amount of resources added up).

> Let's say we're given another QTM with transition $\delta'$ only allowing $O(1)$ gates as a generating set of a dense subset of $SU\_2(\mathbb{C})$, then we redefine the $BQP\_{\delta'}$ with it, is it the case that $BQP\_{\delta'}=BQP\_{\delta}$?

# Answer
After a while I look back on this problem. It turns out using universal gates to generate constant-qubit gates would make no difference to BQP class. The gate complexity, however, depends on $\epsilon$ for the error we try to bound, but precision could be reached in $poly(-\log{\epsilon})$ number of operations.
> 1 votes

---
Tags: complexity-classes, quantum-computing
---


title: Proof involving asymptotic complexity

text:
# Question
Title: Proof involving asymptotic complexity
The question in Proof of big-o propositions asked to prove:

> $O(f(n))=O(g(n))\iff\Omega(f(n))=\Omega(g(n))\iff\Theta(f(n))=\Theta(g(n))$

The accepted answer starts the proof with:

> Suppose that $O(f(n))=O(g(n))$. It is easy to check that $g(n)=O(g(n))$ ... and so $O(f(n))=O(g(n))$ implies that $g(n)=O(f(n))$.

I believe that there is a mistake in quoted part of the answer above.

It claims that $O(f(n))=O(g(n))\tag{1}$

and $g(n)=O(g(n))\tag{2}$

implies

$g(n)=O(f(n))\tag{3}$

Using the interpretation given in "Introduction to Algorithms (CLRS) Edition 3, page 50", (1) is interpreted as $\forall\Phi(n)\in O(f(n)), \exists\Psi(n)\in O(g(n))$ such that $\Phi(n)=\Psi(n)$.

Additionally, the definition of $O$-notation given in "Introduction to Algorithms (CLRS) Edition 3, page 47" states:

> $O(g(n))=\\{f(n):$ there exist positive constants $c$ and $n\_0$ such that $0 \leq f(n)\leq c\cdot g(n)$ for all $n\geq n\_0\\}$

Considering the counter example whereby $f(n)=n$ and $g(n)=n^2$. Then $O(n)=O(n^2)$ and $n^2=O(n^2)$ hold, but $n^2\neq O(n)$, thereby contradicting the assertion given in the accepted answer. Note: "$\neq$" in this case refers to "$\not \in$".

Therefore, I would like to ask if the answer provided is wrong or my interpretation and/or reasoning is wrong.

# Answer
> 0 votes
The notations $a(n) = O(b(n))$ and $O(a(n)) = O(b(n))$ have different meanings:

* $a(n) = O(b(n))$ means that $a(n)$ belongs to the collection of functions $O(b(n))$. That is, $a(n) \in O(b(n))$.
* $O(a(n)) = O(b(n))$ means (in this particular case) that the two collections of functions $O(a(n))$ and $O(b(n))$ are the same. That is, $c(n) = O(a(n))$ iff $c(n) = O(b(n))$.
(Usually $O(a(n)) = O(b(n))$ actually means $O(a(n)) \subseteq O(b(n))$.)

Big O notation is thus ambiguous, but in practice there is usually no confusion.

---
Tags: asymptotics
---


# Question
Title: How to express the data structure in the pesudocode of your algorithm
If I stored the output for my algorithm as a data structure as a cell array. How can I express that when I am writing the pseudocode for my algorithm.

For example, I have a set of $n$ values like {2,4,6} and for each value, I run the algorithm and output a matrix.

I want to express in the pseudocode of my algorithm how I stored the matrix for each value and output these values and the matrices corresponding to it.

# Answer
There are no set rules, but these type of details are sometimes omitted from the pseudocode listing. You might see something like

`ALGORITHM(S, n):
For i = 1 to n do
 S = ADD(S, i)
EndFor`

Then followed by something like "... the algorithm performs $\Theta(n)$ units of work assuming that the set $S$ is implemented as blah so that the addition of an element `ADD(S,i)` runs in blah time ..."
> 1 votes

# Answer
Most of the time, the author explicitly specifies any data structure used and it's operations, For example, if I am using a $ stack $ , I would specify that $ add/push $ operation adds an element to the stack and $ delete/pop/remove $ deletes an element from the stack. When not mentioned, it is advisable to use standard names used by popular programming languages.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Number of final states in minimal DFA for $a^*b^*+b^*a^*$
How many final states exist in the minimal DFA that accepts the language $a^\*b^\* + b^\*a^\*$?

# Answer
Here are the Myhill–Nerode classes of your language:

* $\epsilon$
* $a^+$
* $b^+$
* $a^+b^+$
* $b^+a^+$
* Everything else.

To show this, you have to do two things:

* Show that when in a specific class and reading a specific letter, you go to another specific class. This essentially amounts to constructing a DFA whose states are the classes.
* Show that all the classes are distinct. You do this by giving separating words for every pair of classes.

After that, all that remains to be done is counting how many of these classes correspond to words in the language.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Worst Case Space Complexity of Merge Sort and Bubble Sort
I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(n), linear? All space we need is the exact number of the elements, right? Please enlighten me.

# Answer
Typical implementations of Merge sort use a `new` auxiliary array split into two parts, a left part and a right part. This extra space is the reason for the `O(n)` space complexity.

During the sort section of the algorithm we have the following two new auxiliary arrays created for additional space.

```
int leftPartition[] = new int[ leftPartitionSize ];
int rightPartition[] = new int[ rightPartitionSize ];

```

So, `merge sort` uses auxiliary arrays to sort. However, `quick sort` is an in-place sort that uses `O(1)` space as no auxiliary space is required to sort the data.

Side note: You might also see the space complexity of `merge sort` as `O(nlog(n))`. Some would argue that because of the way the recursive calls to `merge sort` work, the space complexly at any given point is at most `O(n)`. Others might say that adding all the space for all recursive calls requires`O(nlog(n))`. The `log(n)` is because each repeated call to `merge sort` cuts the existing array in half.

If you want true `O(n)` complexity, you can pass an auxiliary array as a parameter into the sort method. Therefore, each call to `merge sort` will use the same array without the need to split the array in half with each call. However, this implementation is quite a bit harder to implement.
> 4 votes

---
Tags: algorithm-analysis, space-complexity, space-analysis, mergesort
---


# Question
Title: Is it theoretically possible to dynamically grow array size in stack memory?
I was wondering, given the usual stack memory functioning, whether it is possible for an array like primitive type allowed to grow in size to exist.
The functioning of such primitive type is as follows.

* Any one function is allowed to have only one such primitive variable.
* Appending to such primitive variable is allowed only within the function that it was initialized in.
* If the function that such primitive variable was initialize in is not the last in the stack, such primitive variable is not allowed to grow in size.

I was wondering whether:

* Such primitive type is theoretically possible.
* Whether it is something that is already in use.

# Answer
Yes, it is certainly possible. It really depends if you want it enough to pay the price in terms of complication.

First of all, I would strongly recommend that your array should have negative indices: `a[-1]`, `a[-2]`, and so on. This will be good because the stack grows *downwards*, and if you adopt this convention then you will not need to move all your existing array elements down to the *new* array position every time you enlarge the array.

After that, it is really a linguistic question. In assembler you can obviously do it, because you can do anything in assembler. Whenever you want your array to be `n` bytes bigger, just subtract `n` from the stack pointer.

In C there is often a function - disapproved of by all respectable computer scientists and therefore very useful when it *is* useful - called `alloca` or `_alloca` \- which allocates `n` bytes of data on the stack and returns a pointer to the new allocation. I would be very surprised if two consecutive `alloca` calls did not just allocate contiguous stack space, so although there isn't a `realloca` function, you could effectively simulate its behaviour.

Where life gets interesting is when the compiler decides to use the stack for its own purposes: for instance, it might precompute the arguments for several function calls and push them all onto the stack before calling any of the functions. Usually such compilers notice a call to `alloca` and disable optimisations in the function that uses it - this is one of the reasons for disapproving of `alloca`.

The main difficulty you would run into would be that, if you wanted your array indices to be "the right way up" - `a[0]`, `a[1]`, `a[2]` and so on - then every reallocation would require data to be moved, which is a bore. **And you can't write your own function in C to do this** (that is, both the extra stack allocation and the data movement) because when you call a function, you usually push a return address onto the stack, so the stack-based array is (as you showed in your pictures) blocked by that extra piece of data and can't be enlarged. You would have to write a special `realloca` function in assembler which pops the return address and keeps it safe; subtracts an appropriate amount from the stack pointer; pushes the return address again; and then does the necessary memory movement. It would actually be quite fun to implement, though not at all portable because different systems will use the stack in different ways in a function call.

---

Is it used? Yes, I have used `alloca` for things I know to be small, because I love not having to rampage all over the heap and I love not having to deallocate. But your more elaborate scheme - I haven't heard of anyone who has done it.

Except in assembler - where one can do a beautiful merge sort by using the stack to store data.
> 4 votes

---
Tags: stacks, memory-allocation
---


title: Why is $ZPP \geq BPP$ not true?

text:
# Question
Title: Why is $ZPP \geq BPP$ not true?
This seems like a silly question, but I couldn't find a conclusive answer for it.

As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or abort (this definition is equal to the one where they either return a correct answer or run in exponential time). It is also possible to get the failure probability of a ZPP algorithm arbitrarily low (but $\>0$) by rerunning it often enough without using exponential time.

BPP contains algorithms which will always return an answer in polynomial time, but this answer may be wrong with at max a $\frac{1}{3}$ chance.

Therefore, given a solver for ZPP problems, I can create a function which either solves my problem or abort in $\frac{1}{3}$ of the cases, while running in polynomial time$^1$.

Given this function, I can solve any problem contained in BPP by running the function created above on it and return a random response if it aborts. Since this will be in less than $\frac{1}{3}$ of the cases, the probability for a wrong answer will be less than $\frac{1}{3}$ and it will always run in polynomial time.

This would imply that BPP is contained in ZPP, but it seems that it is actually the other way around. So where am I wrong?

$^1$ This might be my error, but it's described like this in our lecturer slides (which are not public). I couldn't find a direct citation for it, but Complexity Zoo states for RP: "*implicitly: the class VPP that is defined is equivalent to RP by running the recognizer as many times as necessary to reach probability 1/2?*", so I assume this can be applied to ZPP as well and my understanding is correct. EDIT: Also, in case this doesn't hold true, at least ZPP($\frac{1}{3}$) should be equal to BPP, which I couldn't find anywhere either.

# Answer
> 2 votes
You explain how to convert a ZPP machine to a BPP machine. This means that if a problem is in ZPP, then it is also in BPP. In other words, ZPP is contained in BPP.

---
Tags: complexity-theory, reductions, randomized-algorithms
---


# Question
Title: Average Case Running Time of Quicksort Algorithm
From this website, it states that the average case of Quicksort algorithm is

```
  T(n) = T(n/9) + T(9n/10) + θ(n)

```

Im a bit confused. Is it supposed to be ?

```
  T(n) = T(n/10) + T(9n/10) + θ(n)

```

# Answer
The average case running time of quicksort satisfies the recurrence $$ T(n) = \frac{1}{n} \sum\_{i=1}^n \[T(i-1) + T(n-i)\] + \Theta(n), $$ with base case $T(0) = \Theta(1)$.

In view of solving this recurrence, let us replace $\Theta(n)$ with $n+1$ and $\Theta(1)$ with $2$ (the reason for these specific choices will become apparent below). Changing the order of summation, we get $$ T(n) = \frac{2}{n} \sum\_{i=0}^{n-1} T(i) + n + 1, $$ and so $$ nT(n) = 2\sum\_{i=0}^{n-1} T(i) + n(n+1). $$ This implies that $$ (n+1)T(n+1) - nT(n) = 2T(n) + 2(n+1), $$ and so $$ T(n+1) = \frac{n+2}{n+1} T(n) + 2. $$ Unrolling this gives $$ \begin{align\*} T(n) &= 2 + \frac{n+1}{n} T(n-1) = 2 + \frac{n+1}{n} 2 + \frac{n+1}{n-1} T(n-2) = \cdots \\ &= 2\left\[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2}\right\] + \frac{n+1}{1} T(0) \\ &= 2\left\[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2} + \frac{n+1}{1} \right\] \\ &= 2(n+1) \left\[\frac{1}{n+1} + \cdots + \frac{1}{1} \right\] \\ &= 2(n+1) H\_{n+1} \\ &= \Theta(n\log n). \end{align\*} $$

---

A different way of analyzing the running time of quicksort in the average case computes the average number of comparisons. Due to linearity of expectation, it suffices to calculate the probability that two elements are compared. You can see both methods worked out in Section 3.4 of lecture notes from CMU.
> 4 votes

---
Tags: algorithm-analysis, runtime-analysis, quicksort, average-case
---


# Question
Title: Steiner tree problem in graphs of diameter 3
I have an unweighted undirected graph $G(V, E)$ of diameter 3 and a subset $T\subseteq V$ of these vertices. I want to find the minimum tree $(V', E')$ that contains all vertices in $T$, minimizing the number of nodes $|V'|$.

Is it true that $|V'|\le 2|T|$? If $G$ is of diameter 2 it is easy to prove that this is true. Also for diameter 4, it is not true always since we can take a path graph of 5 vertices with $T$ as two leaves.

# Answer
This is an interesting question.

It is not true that $|V'|$ is always less than or equal to $2|T|$. Here is the smallest example of $G$ and $T$ where $|V'|$ must be greater than $2|T|$.

Graph $G$ as depicted above has 9 vertices $A,A\_1,A\_2,B,B\_1,B\_2,C,C\_1,C\_2$ and 12 edges $AA\_1, A\_1A\_2, A\_2A,$ $BB\_1,B\_1B\_2,B\_2B,$ $CC\_1, C\_1C\_2, C\_2C,$ $A\_1B\_2, B\_1C\_2, C\_2A\_1$. It is easy to check the diameter of $G$ is 3.

Let $T=\\{A,B,C\\}$. Suppose $T'=(V',E')$ is a minimal tree in $G$ that spanns $T$.

* If $V'$ contains all 9 vertices, then $|V'|=9$.
* Otherwise, WLOG, assume $V'$ does not contain $A\_1$. If anyone of $A\_2$, $C\_1$, $C\_2$ and $B\_1$ is not in $T'$, then $A$ and $B$ will not be connected in $T'$. Since $A$ and $B$ are connected in $T'$, all of those 4 vertices must be in $T'$. So $|V'|\ge3+4=7$.

So $|T'|\gt 6= 2|T|.$

**Exercise 1**. Verify that the following two graphs are also examples where $|V'|$ must be greater than $2|T|$ with $T=\\{A, B, C\\}$

**Exercise 2**. (less than 1 minute) If $|T|=3$, then $|V'|\le7$.

**Exercise 3**. Let $n\ge3$. Construct $G$ and $T$ such that $G$ is connected of diameter 3, $|T|=n$ and $|V'|\gt 2|T|$. (Hint, imitate the simpler example in exercise 2.)
> 3 votes

---
Tags: graphs, computational-geometry, discrete-mathematics
---


title: Create NOT gate from other gates

text:
# Question
Title: Create NOT gate from other gates
If we are given only one NOT gate and any number of OR and AND gates, then, can we simulate more NOT gates?

# Answer
> 5 votes
Consider a circuit having a single NOT gate, computing some function $f(x)$. We can write $f(x) = g(x,\lnot h(x))$, where $g,h$ are monotone functions.

Consider now a sequence of inputs $x\_0 \< x\_1 \< \cdots \< x\_n$ (i.e., $x\_0$ is the zero input, and $x\_i$ is obtained from $x\_{i-1}$ by changing one bit from 0 to 1). Since $h$ is monotone, it is either constant on $x\_0,\ldots,x\_n$, or $h(x\_0) = \cdots = h(x\_i) = 0$ and $h(x\_{i+1}) = \cdots = h(x\_n) = 1$ for some $i$. In the former case, $f(x\_0) \leq \cdots \leq f(x\_n)$. In the latter case, $f(x\_0) \leq \cdots \leq f(x\_i)$ and $f(x\_{i+1}) \leq \cdots \leq f(x\_n)$. This means that the sequence $f(x\_0),\ldots,f(x\_n)$ flips from 1 to 0 at most once.

It follows that the complement of the parity function on three bits cannot be computed using a single NOT gate. Indeed, if it could, then consider $x\_0=000$, $x\_1=001$, $x\_2=011$, $x\_3=111$. Then $f(x\_0),f(x\_1),f(x\_2),f(x\_3)=1,0,1,0$ flips twice from 1 to 0.

This shows that you cannot simulate an arbitrary number of NOT gates using a single NOT gate.

---
Tags: computer-architecture, logic
---


# Question
Title: How would one simulate the law of conservation of energy?
I'm new to computer science, but I've studied physics for a while. I'm just curious, if one wanted to make a simulation of the law of conservation of energy, on a large scale, how would it be done? Most simulations take shortcuts for objects off screen, or may even skip them entirely during iterations. The objects may be frozen in place of screen, or grouped together if not interacting. Can these tricks be applied when simulating conservation of energy, without violating the law? Thanks.

# Answer
I'm having a lot of trouble understanding the question as posed, but I think it's worth making a few general comments about conservation laws and how they are used in physical simulation.

Conservation laws happen because of Noether's theorem. When you are investigating how some physical system evolves over time, it's usually the case that the exact moment when $t=0$ is an arbitrary choice; you could start it 10 seconds later and the system would evolve the same. This is known as time translation symmetry. Any physical system which is time translation invariant is a system where energy is conserved.

Let's take as an example the problem of simulating a gas, where viscosity can be ignored, in one dimension.

We denote $\rho(x,t)$ as the density of the gas at a time and place, $v(x,t)$ is the velocity, $E(x,t)$ is the energy, and $p(x,t)$ is the pressure.

Then the equations we are solving are the Euler equations:

$$\frac{\partial}{\partial t} \rho + \frac{\partial}{\partial x} \rho v = 0$$ $$\frac{\partial}{\partial t} \rho v + \frac{\partial}{\partial x} \left( \rho v^2 + p \right) = 0$$ $$\frac{\partial}{\partial t} E + \frac{\partial}{\partial x} v\left(E + p\right) = 0$$

The pressure is defined in terms of the other variables, called the "equation of state". If we assume an ideal gas, $E = \frac{p}{\gamma - 1} + \frac{1}{2} \rho v^2$ where $\gamma$ is the heat capacity ratio, which is different for different gases.

The Euler equations are, respectively, conservation of mass, conservation of momentum (note that $\rho v$ is momentum), and conservation of energy. The equations state that a local change of (say) energy in time is balanced exactly by a change in space. So those three conservation laws are, in a deep sense, exactly the system that you are trying to simulate.

So I think that it's misleading to think of conservation of energy as something to exploit in simulating some physical system. Conservation of energy *is* a central part of the system that you're trying to simulate.

One last thing: Physical simulation, especially of thermodynamic systems, suffers from a phenomenon known as "numerical dissipation" or "numerical dispersion". The fact that you are using discrete time steps to simulate a continuous system means that something has to give, and depending on the numerical methods that you are using, this sometimes translates as unwanted diffusion of some quantity that should be locally conserved. Like energy.
> 1 votes

---
Tags: simulation
---


# Question
Title: information theory, find entropy given Markov chain
There is an information source on the information source alphabet $A = \\{a, b, c\\}$ represented by the state transition diagram below:

a) The random variable representing the $i$-th output from this information source is represented by $X\_i$. It is known that the user is now in state $S\_1$. In this state, let $H (X\_i|s\_1)$ denote the entropy when observing the next symbol $X\_i$, find the value of $H (X\_i|s\_1)$, entropy of this information source, Calculate $H (X\_i|X\_{i-1}) $ and $H (X\_i)$ respectively. Assume $i$ is quite large

How can I find $H(X\_i|s\_1)?$ I know that $$H(X\_i|s\_1) = -\sum\_{i,s\_1} p\left(x\_i, s\_1\right)\cdot\log\_b\\!\left(p\left(x\_i|s\_1\right)\right) = -\sum\_{i,j} p\left(x\_i, s\_1\right)\cdot\log\_b\\!\left(\frac{p\left(x\_i, s\_1\right)}{p\left(s\_1\right)}\right)$$ but I don't know $p(s\_1)$.

$$A=\begin{pmatrix}0.25 & 0.75 & 0\\0.5 & 0 & 0.5 \\0 & 0.7 & 0.3 \end{pmatrix}.$$

From matrix I can know that $p(s\_1|s\_1)=0.25$, etc.

But what is the probability of $s\_1$? And how can I calculate $H (X\_i|X\_{i-1})$?

# Answer
You can make the golloowing set of equations, where s1 - the probability of being in s1 state:

```
s1 = 0.25s1 + 0.5s2
...
s1+s2+s3=1

```

I don't know the theory, but think that entropy of each state can be computed as follows:

```
e1 = - 0.25*log(0.25) - 0.75*log(0.75)

```

with overall entropy given already computed probability and entropy of each state

```
e = e1*s1 + e3*s3 + e3*s3

```

I don't know what H(...) means.
> 0 votes

---
Tags: probability-theory, information-theory, entropy, markov-chains
---


# Question
Title: Longest common substring many strings to one
I'd like to find longest common substring (occurrences, start index) between one string and many others.

**For example**

* source string - "abcdefghijklmncdop"
* other strings - \["cd", "ghi", "mn", "zw", "cdewxyz"\].
* Expected result -(original string, substring, index in source string) = \[(cd,cd,2),(cd,cd,14),(ghi,ghi,7 ),...(cdewxyz, cde, 3\]

I could create suffix array from the source string and search all possible substring occurrences sequentially - but it doesn't seem that efficient. The other strings array might be very large, so creating joint arrays with special delimiter is not considered.

I also thought on creating suffix tree, but I there are many source strings soe space complexity might become an issue.

# Answer
Let's assume you have already built suffix tree for string $S$. Then for any string $T$ you can find $\mathtt{LCS}(S, T)$ in $\mathcal{O}(|T|)$ time, $\mathcal{O}(1)$ space, and read-only access to the suffix tree.

Here's pseudocode that finds $M$ \- location in the suffix tree (edge plus position on that edge) that corresponds to $\mathtt{LCS}(S, T)$:

```
M := C := ST.root

for i := 1..|T| do
  while C.canNotExtendWith(T[i]) do
    C := C.contract()

  C := C.extendWith(T[i])

  if C.length > M.length then
    M := C

```

Here:

1. `ST.root` is the suffix tree root
2. `C.canNotExtendWith(x)` returns true if you can't follow given letter $x$ from location $C$
3. If $C$ is a location of string $U$ in the tree, then `C.extendWith(x)` returns location of string $Ux$
4. If $C$ is a location of string $xU$, then `C.contract()` returns location of $U$ (i.e. follows the suffix link)
5. If $C$ is a location of string $U$, then `C.length` is $|U|$

Both correctness and $\mathcal{O}(|T|)$ time complexity follow from the Ukkonen's algorithm.

Hand-wavy explanation of the algorithm correctness:

1. If you can't extend the substring with single letter, there's no point in trying to extend it further
2. If you've already found a good candidate substring, there's no point in contracting it
> 1 votes

# Answer
I suspect there's nothing better than the following iterative algorithm: for each $i$ in $1,2,\dots,n$, find the longest common substring between $S$ and $T\_i$ (where $S$ is the one string and $T\_1,\dots,T\_n$ are the other strings).

If you only want to find a longest common substring between $S$ and $T\_i$, this can be done in linear time, i.e., $O(|S|+|T\_i|)$ time, where $|S|$ is the length of the string $S$ and $|T\_i|$ is the length of the string $T\_i$. There are many ways to do it in linear time; for instance, you can concatenate them with a delimiter and then use a suffix tree or a suffix array. If you want to find all common substrings of that length, it takes $O(|S|+|T\_i|+m)$ time, where $m$ is the number of such substrings, if you're satisfied with printing out just the indices where these substrings exist; if you also want to also print out the strings themselves, then the running time is $O(|S|+|T\_i|+mk)$, where $k$ is the length of the longest common substring.

If you want to do this between $S$ and each of the $T\_i$'s, sum this up over all the $i$'s.

The space complexity is $O(|S|+\max\_i |T\_i|)$, since you can throw away the data structure for $S,T\_i$ after you're finished with $T\_i$ and before you start with $S,T\_{i+1}$.
> 0 votes

# Answer
The answer greatly depends on practical details. One possible algorithm is the following:

1. Build SA from the source string
2. Sort other strings (it will be O(N + TotalLength) using radix sort) into OA
3. Split one of two arrays (SA or OA) into two halves and find the corresponding point in the opposite array
4. Repeat the last step recursively, until you find position pair in SA for each string of OA
> 0 votes

---
Tags: substrings, suffix-trees, suffix-array
---


title: Descriptive complexity of 3SAT

text:
# Question
Title: Descriptive complexity of 3SAT
lately I'm reading about descriptive complexity, which I find is a fascinating branch of computational complexity. I found many formulas in $\exists$$SO$ that describe problems with graphs but none that describes the 3SAT language.

Thinking about it, I came to an "atomic" description like this:

$\exists$$v$$\forall$$C$ $(P(C))$

Where $v$ is a *literal*, $C$ is a *clause* (i.e. the $OR$ of 3 literals) and $P(C)$ means that $C$ is true.

However I'm not satisfied with this definition, I don't think it captures the complexity of the 3SAT language, especially the dependence of the variables on one another. Can you tell me a correct formula to describe this decision problem? Thank you.

# Answer
> 2 votes
The language consists of ternary relations $R\_1, \dots, R\_4$, which represent the clauses as follows:

* $(x,y,z)\in R\_1$ iff there is a clause $(x\lor y\lor z)$;
* $(x,y,z)\in R\_2$ iff there is a clause $(x\lor y\lor \neg z)$;
* $(x,y,z)\in R\_3$ iff there is a clause $(x\lor \neg y\lor \neg z)$;
* $(x,y,z)\in R\_4$ iff there is a clause $(\neg x\lor \neg y\lor \neg z)$.

($\lor$ commutes so you don't need to consider other patterns of negation.)

The formula then says "There exists a set $T$ of variables such that, if the variables in $T$ are set to true and the ones not in $T$ are set to false, the formula is satisfied." That is,

$$\begin{align\*} \exists T\\,\forall x\forall y\forall z\\, \big\[&\big(R\_1(x,y,z)\rightarrow (T(x)\lor T(y)\lor T(z))\big)\\ &\quad \land \big(R\_2(x,y,z)\rightarrow (T(x)\lor T(y)\lor \neg T(z))\big)\\ &\quad \land \dots\big\]\\,. \end{align\*}$$

---
Tags: decision-problem, 3-sat, descriptive-complexity
---


title: Substructural Prolog?

text:
# Question
Title: Substructural Prolog?
Substructural logic is logic without some or all of the structural rules. Is substructural Prolog, substructural logic programming possible? My question is connected with article https://link.springer.com/chapter/10.1007/3-540-40030-3\_8 *Grammar Induction as Substructural Inductive Logic Programming* \- if substructural Prolog is possible then one can implement substructural inductive logic programming in it (e.g. http://ilasp.com/ for the answer set version of ILP over Prolog in the non-substructural setting) and apply, e.g. in grammar induction case.

How hard the usual (e.g. SWI) Prolog should be remade to be used as substructural Prolog?

# Answer
> 4 votes
Logic programming with substructural logics has been studied, starting in the second half of the 90's. I am not an expert, but I can probably provide enough references to get you going.

There is Dale Miller's Lolli, a programming language for linear logic programming.

Major research was carried out by Frank Pfenning and his coworkers and students. For example:

I am pretty sure someone implemented logic programming for ordered linear logic, poke around the work done by Jeff Polakow and Frank Pfenning. I don't seem to be able to find it right now.

---
Tags: formal-languages, logic, prolog
---


# Question
Title: Underlying codes for Niederreiter cryptosystems
Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}\_{2^n}$.

The minimum distance $d$ is given by

$d := min\lbrace k \text{ such that there are $k$ linearly dependant columns in $H$}\rbrace$

Encryption in this case is done by encoding messages $m$ of weight less than $d/2$.

Now keeping Niederreiter systems in mind, my question is, since $m$ is over $\mathbb{F}\_2$, it makes sense to consider linearly dependence over $\mathbb{F}\_2$ rather than $\mathbb{F}\_{2^n}$. In other words, is it okay to consider code as a code over $F\_{2}$ with alphabet extension or do we have to consider it as codes over $\mathbb{F}\_{2^n}$.

# Answer
According to Sendrier, Niederreiter systems are only known to be secure when used with Goppa codes. All other families of codes which have been tried have been broken. You are suggesting a code superficially related to the Goppa code but probably having very different properties. Hence it is likely to be insecure (or perhaps useless for other reasons, such as low rate or low distance).

More generally, cryptosystems are surprisingly brittle. I would leave them to the experts.
> 1 votes

---
Tags: cryptography, linear-algebra, coding-theory
---


# Question
Title: Number of ways painting graph in two colors, such that two nodes of same color are linked by edge
We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must be an edge between them.

I tried some examples on paper and I always got numbers of the form $2^x$, however I couldn't see a valid way to find such $x$ or I couldn't prove why this is the case.

Does this problem become easier if we are given directed acyclic graph instead of undirected one?

# Answer
> 1 votes
Call a coloring where two nodes of same color must be linked by an edge (a.k.a. adjacent) attractive-coloring. The more common node coloring, where no two adjacent nodes are of the same color will be called repulsive-coloring.

Let $G$ be a given graph and $G'$ be the complement graph of $G$, i.e., $G'$ and $G$ are on the same nodes such that two distinct nodes of $G'$ are adjacent if and only if they are not adjacent in $G$.

An attractive-coloring of $G$ is an repulsive-coloring of $G'$ and vise versa. So the number of attractive-2-colorings of $G$ is the number of repulsive-2-colorings of $G'$. Note that a 1-coloring is considered a 2-coloring.

A graph can have a repulsive-2-coloring if and only if it is a bipartite graph. A connected bipartite graph has exactly two repulsive-2-coloring, i.e., assuming the two colors are red and black, we can color all nodes in one group red and all nodes in the other group black or the other way around.

Suppose the connected components of $G'$ are $C\_1, C\_2, \cdots, C\_k$. If one of them is not bipartite, then there is no repulsive-2-coloring for that component and hence no repulsive-2-coloring for $G'$. If all of them are bipartite, then there are two repulsive-2-colorings for each of them and hence $2^k$ repulsive-2-colorings of $G'$.

**Exercise** (the well-known theorem on 2-colorable graphs). The (repulsively-)2-colorable graphs are exactly the bipartite graphs.

---
Tags: graphs, counting
---


# Question
Title: O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question
Question: Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice. The second buy has to come after first sell.

Solution: There is a O(N) time and O(N) space complexity solution, that keeps track of the maximum profit that can be made when selling at day i in a N size array. Then it calculates the max profit by using this array in conjunction with max profit that can be made by buying at day i+1.

I would appreciate any hints on how I can get a O(N) time and O(1) space complexity solution?

# Answer
Here's an O(1) space, O(n) time algorithm with Java code.

**Logic:**

---

Let $P\_i$ denote the price of the stock on day $i$.

* Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P\_i - min\[P\_0...P\_{i-1}\])$. Call this $MaxProfit1\_i$.
* If you had sold before day $i$ you can buy again at day $i$. If you do so, you'll need to deduct day $i$'s price from the 1st transaction's profit. Then, the maximum leftover profit at day $i$ is $Max(P\_i - MaxProfit1\_i)$. Call this $MaxLeftOver\_i$.
* In the same vein, if you had bought the 2nd stock before day $i$, you can sell it at day $i$. If you do so, you add day $i$'s price to the previous leftover profit to arrive at your profit at day $i$ with 2 transactions. Then, the maximum profit at day $i$ with 2 transactions is $Max(P\_i + MaxLeftOver\_i)$ \- which is the final answer.

```
public int maxProfitWith2Transactions(int[] prices) {
    if (prices.length == 0) return 0;

    int minPrice                      = prices[0];
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int i = 1; i < prices.length; i++) {
        final int p = prices[i];
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell);
        minPrice                    = Math.min(p, minPrice);
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
    }
    return maxProfitAfterSecondSell;
}

```

The below modified (slightly faster) variant of the above beats every solution in both space and time on LeetCode.

```
public int maxProfitWith2Transactions(int[] prices) {
    int minPrice                      = Integer.MAX_VALUE;
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int p : prices) {
        minPrice                    = Math.min(p, minPrice);
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell);
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
    }
    return maxProfitAfterSecondSell;
}

```

Here's the values that the above code calculates for prices `8, 10, 3, 7, 4, 9, 2, 3`. Clearly, the max profit after 1 transaction is 6 (Buy at 3, sell at 9). After 2 transactions, the max profit is 9 (Buy at 3, Sell at 7, Buy again at 4, sell at 9).

$$\begin{array}{l|r r r r r r r r} \text{$i$} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} \\ \hline \text{Price} & \text{8} & \text{10} & \text{3} & \text{7} & \text{4} & \text{9} & \text{2} & \text{3} \\ \\ \hline \text{Lowest price seen} & \text{8} & \text{8} & \text{3} & \text{3} & \text{3} & \text{3} & \text{2} & \text{2} \\ \text{till day $i$} \\ \hline \text{Max Profit if} & \text{x} & \text{2} & \text{2} & \text{4} & \text{4} & \text{6} & \text{6} & \text{6} \\ \text{bought at lowest} \\ \text{price before day $i$} \\ \text{and sold before} \\ \text{or on day $i$} \\ \hline \text{Max Profit left if} & \text{x} & \text{-8} & \text{-1} & \text{-3} & \text{0} & \text{0} & \text{4} & \text{4} \\ \text{2nd buy is done on} \\ \text{day $i$.} \\ \text{= Max(PreviousRow$\_i$ - $P\_i$)} \\ \hline \text{Max Profit if 2nd} & \text{x} & \text{2} & \text{2} & \text{4} & \text{6} & \text{9} & \text{9} & \text{9} \\ \text{stock is sold before} \\ \text{or on $P\_i$} \\ \text{= Max(PreviousRow$\_i$ + $P\_i$)} \\ \hline \end{array}$$
> 8 votes

# Answer
**Hints:**

The goal is to pick four values from the sequence such that

$$\frac{v\_j}{v\_i}\frac{v\_l}{v\_k}$$ is maximized. The solution is made of the two ratios that fulfill the order constraint while maximizing the product.

The best ratio in an interval is given by the maximum over the minimum, which you can find in time proportional to the interval size. You can also update the best ratio incrementally when you lengthen the interval, by recomputing the minimum and maximum.

If you sweep the whole array, you can obtain the best ratios on the left and right subarrays and compute their product. This is done in linear time on the left side (incrementally). So far, I have not found the trick to achieve linear time on the right (because the interval shrinks rather than lengthens).
> 2 votes

# Answer
At any point in time, you have either (a) not bought anything, (b) bought stock once, (c) bought and sold stock once, (d) bought and sold, then bought again, (e) bought and sold twice. In each case you have a certain amount of cash and a certain number of shares. Initially, you have all cash and zero shares in state (a); to simplify the algorithm assume that you might be in states (b) to (e) with a buy/sell of zero shares.

At each point when the share price is known, you could switch say from state (a) to (b), and you do that if the result is better than a previous state (b). Or switch from state (b) to (c) etc. You need only a fixed amount of memory for these five states, and O (n) comes from processing n new share prices.
> 1 votes

# Answer
```
denote d[n] as array. index from 0 ~ e  where e = (n - 1)
trans(i, j) = max(d[k2] - d[k1])  subject to:  k2 > k1 and k2 <= j  k1 >= i
k1, k2 = argmax(trans(i, j))  k1 means buy point   k2 means sold point
split(k) = trans(0, k) + trans(k+1, e)
we need to get max(split(k), subject to: 0 <= k <= e)

(1) caculate: i, j =  argmax(trans[0, e])
note the property:
     d[k] > d[i]  when k < i
     d[k] < d[j]  when k > j
     d[i] < d[k] < d[j] when i < k < j

(2) easy to prove:
    split(k) <= split(i) when k <= i
    split(k) <= split(j) when k >= j
    caculate: trans(0, i-1) and trans(j+1, e)

(3) caculate  split(k)  when  i < k < j
   split(k) = trans(0, k) + trans(k+1, e)
   consider:
   trans(0, k) , A if sold before i,  trans(0, k) = trans(0, i-1)
                 B if sold after i, must buy  i

   consider:
   trans(k+1, e), C if buy after j, trans(k+1, e) = trans(j+1, e)
                  D if buy before j, must sold j

   consider  all casees:
   split(k) = max( A + C, A + D, B + C, B + D)
   A + C = tran(0, i - 1) + trans(j+1, e)
   B + D,  a similary problem:   sold max and buy min between d[i+1] , d[j-1], will token o(n) time complexity
   A  + D /  B + C   we   iterate on all possible k

```
> -1 votes

---
Tags: algorithms, optimization
---


title: Weight functions in graph algorithms

text:
# Question
Title: Weight functions in graph algorithms
In text books, for instance in the 3rd edition of *Introduction to Algorithms*, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$.

Why is it defined in this way? Why do we need a function? I mean, we all know when working with a graph, that the meaning is just that an edge $(u,v)$ has a weight $w$. So, why is it written with a function? I remember the first time I saw this definition I was very confused. Only after actually going through an algorithm and reading it again, I realized that it really just means that every edge has its weight.

So, I still don't fully understand why it is written in this complicated way and what exactly it means though, and it would be very nice if someone could tell me that in a understandable language.

# Answer
> 7 votes
Here is the original statement in CLRS.

> Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$.

It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush or subconsciously. It is good enough in most situations. I would encourage you to keep this primitive understanding, as it may help forming the most compact and natural representation of knowledge in your mind.

Should we read aloud that notation, we can say "$w$ from $E$ to $\Bbb R$" or "$w$ from capital $E$ to bold $\Bbb R$" literally. Adding a bit of interpretation, we can also say, "function $w$ from edges to real numbers", "function $w$ that maps each edge to a real number", or, even more explicitly, "function $w$ whose domain is the set of edges and whose codomain is the set of real numbers".

While the simple and natural understanding, "an edge has a weight", is probably enough to understand the setup for that section of the book, that mathematical notation has some distinct advantages.

In general, although expressive and colorful, natural languages or thoughts, are more complex and abound with ambiguity and arbitrary vagueness. If "an edge $(u,v)$ has a weight $w$", is weight something like "2 miles", "5.0 dollars", or "approximate 7.7 pounds"? Could the edge $(u,v)$ also have an extra weight? Should I use the same symbol $w$ for the weight of edge $(u,v')$ that is not edge $(u,v)$? While these questions may or may not pose a problem for you, it might for other readers of the book.

On the other hand, the notation "$w: E\to\Bbb R$" defines exactly what is the domain, codomain and the kind of correspondence of a relation. To be pedantic, it means the symbol/entity $w$ associates to every element of $E$, i.e, an edge of $G$ exactly one element of $R$, i.e, a real number. There is no room to err.

Moving down the road, page 648 of the book presents the following formula.

> $\begin{aligned} w(T') &= w(T) - w(x,y) + w(u,v)\\ &\le w(T) \end{aligned}$

If you try to express the facts embodied in the above formula in plain English, more than two or even five times longer statements may be needed to attain the same rigor and clarity. The result can hardly be more visually appealing. That is how the notation $w:E\to\Bbb R$ shines.

The power of mathematics notations, including notations in computer science, is what you would like to master if you want to dive further into the mathematics, computer science and many other subjects where symbolic computations are needed and useful. In a sense, notations like this are beautiful data types. You can get familiar with them. You can become comfortable with them.

# Answer
> 5 votes
It means that **each** edge has **only one** weight, which is defined as a **real** number.

So, this definition in compact form excludes many cases, for example:

* an edge doesn't have weight at all
* an edge has two (or more) weights
* an edge has weight as a complex number
* etc.

---
Tags: graphs, weighted-graphs, notation
---


# Question
Title: Is every Turing complete set for EXPSPACE autoreducible?
I'm reading about autoreducibility, which is the following notion:

> A set $L$ is autoreducible if there is a polynomial-time oracle Turing machine $M$ that accepts $L$ using $L$ as an oracle, with the caveat that $M(x)$ may not query whether $x \in L$.

I encountered some results that are confusing me. In Using autoreducibility to separate complexity classes, Buhrman et al. showed that every polynomial-time Turing-complete set for EXPSPACE is autoreducible (Theorem 4.1). In Diagonalization, a survey by Fortnow, there is a theorem stating that if every Turing-complete set for EXPSPACE is autoreducible then $NL \neq NP$ (Theorem 3.1). So using both theorems together, we have $NP \neq NL$! I want to know where is my fault.

# Answer
> 1 votes
The result from Buhrman et al. is about EXP rather than EXPSPACE.

Note that Theorem 3.1 from Fortnow's survey is taken from the very same paper of Buhrman et al.

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


# Question
Title: Decomposition of a directed graph into Hamiltonian paths
I was wondering if anyone knew of an algorithm that when given a directed graph will split it up into separate Hamiltonian paths. I don't really mind about nodes that can't be added to a path but as few paths as possible should be made to include the most nodes.

Any ideas would be greatly appreciated.

# Answer
Finding an Hamilton path in directed (and un-directed) graphs, is an $NP$ complete problem. Thus, there is probably no efficient algorithm (polynomial) to split a given graph to several hamiltonian paths.
> 1 votes

---
Tags: algorithms, graphs, hamiltonian-path
---


title: Minimum Bounding Quadrilateral

text:
# Question
Title: Minimum Bounding Quadrilateral
In an image processing project (using opencv with python), I am trying to detect as precisely as possible the location of a rectangular object in a photograph. My final goal is to output the 4 corners of the object.

For example, an image could look like this:

In the first stage I am able to detect an approximate boundary for the image, like so:

Now, I have the above red convex polygon.

Next, I would like to compute the **Minimum Area Bounding Quadrilateral**, and this is where I'm stuck.

My question is, given a convex polygon, what is an efficient algorithm to find a minimum area bounding quadrilateral?

Thanks!

# Answer
The fitting of a minimum area quadrilateral to a set of points is an uneasy problem, and I believe that simpler approaches are good enough.

Notice that the corners are rounded and cannot be used as such. So you'd better fit straight edges and intersect them to obtain the quadrilateral.

One approach is by the Hough transform. To make it maximally efficient, I would recommend to process four tight areas or interest around the edges of the axis-aligned bounding box. This will make processing much faster, avoid false positives and avoid any ambiguity on the correspondences.

You can also sample points on the four sides and fit a straight line by total-least squares, or by some robust line fitting method.

If you want to make sure that the fitted lines don't cross the shape at all, you can handle the four sides independently and consider a partition of the plane in the four quadrants delimited by the diagonals (even if they are approximate). In every quadrant, you will find the minimum area triangle formed by the line against an edge of the convex hull. Just try every edge of the convex hull in turn.

\[Technically, it is possible that the minimum is achieved with a line through some vertex of the convex hull, with an intermediate angle, i.e. not in the direction of a hull side. We should also check if the area function is always unimodal in terms of the line angle. IMO these refined considerations can come later.\]
> 2 votes

---
Tags: algorithms, computational-geometry, image-processing
---


title: Run time for a specific loop confusion

text:
# Question
Title: Run time for a specific loop confusion
I have a loop: `for(int i = 1; i < N; i*=5) {...}`

where `{...}` is some statement.

I'm trying to understand its run time. So, far I know that:

* We start with $i = 1$
* We finish when $i \> n$
* $i$ is incremented by being multiplied by 5.

So, would the run-time be $\log\_5(n-1)$? The reason I'm not sure it's because I thought when analyzing algorithms we had to use base 2 log functions. If the latter is the case how would I got about converting $\log\_5$ to $\log\_2$?

# Answer
> 3 votes
A basic result in elementary arithmetic states that $$ \log\_a n = \log\_a b \cdot \log\_b n. $$ Indeed, on the one hand, $a^{\log\_a n}$ by definition. On the other hand, $$ a^{\log\_a b \cdot \log\_b n} = (a^{\log\_a b})^{\log\_b n} = b^{\log\_b n} = n. $$ Similarly, $$ \log\_b n = \log\_b a \cdot \log\_a n. $$ This shows that every two logarithms only differ by a constant multiple. Since big O notation discounts constant factors, it doesn't matter which logarithm you use (unless it's in the exponent). For example, a function is $O(\log\_a n)$ iff it is $O(\log\_b n)$. For this reason we usually don't bother writing the basis of a logarithm in big O notation.

# Answer
> 1 votes
I don't know what you intended to write, but your loop runs in constant time if N \<= 0, and will never finish if N \> 0.

If you start with i = 0, and multiply i by 5, guess what: It's still 0. I really can't see how you get to $i^5$. After k iterations, the initial value of i is replaced with $i * 5^k$; since the initial value is 0, it stays 0, and the loop never exits if N \> 0.

If you started with i = 1, it would be extremely unlikely that you would ever get i = N-1. For example, the loop will exit with i = 3,125 with the last iteration i = 625 for all 625 \< N ≤ 3,125. Only when N is one larger than a power of 5 will i ever equal N-1 (if we start with i = 1).

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