# Question
Title: Duplicate elements in Queue for BFS Maze Algorithm
I'm fairly new to studying data structures and algorithms.

I've implemented a non-recursive BFS on a 2d "maze array" which seems to work well. It finds the position of 2 in an array of 1s (walls) and 0s (spaces), marking visited positions with 3.

However, I notice that there are duplicate values in the Queue. I understand that I should avoid visiting already visited positions. However the queue contains only "prospective" positions which are yet to be visited. Should I modify the algorithm to not enqueue positions which it already contains? Will the algorithm still work if I do so?

As far as I know I have implemented the following algorithm:

```
Create a queue for positions yet to explore, and enqueue the entrance (0,0)
While the list is not empty
     dequeue
     If it is the goal position,
            exit displaying position and success message
     Otherwise,
            mark the position as visited, and enqueue all valid neighbors (not walls and not visited)
If the list is empty and the method has not returned, there is no path

```

Some sample output is below:

```
Enqueueing (0,0)
Queue contents: [(0, 0)]
Press Enter to continue:
Dequeueing
Current position: (0, 0)
Marking (0, 0)
[3, 1, 1, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(0, 1)]
Press Enter to continue:
Dequeueing
Current position: (0, 1)
Marking (0, 1)
[3, 1, 1, 0]
[3, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 1), (0, 2)]
Press Enter to continue:
Dequeueing
Current position: (1, 1)
Marking (1, 1)
[3, 1, 1, 0]
[3, 3, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(0, 2), (2, 1), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (0, 2)
Marking (0, 2)
[3, 1, 1, 0]
[3, 3, 0, 1]
[3, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 1), (1, 2), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (2, 1)
Marking (2, 1)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 2), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (1, 2)
Marking (1, 2)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 2), (1, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 2)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 3), (1, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 3)
Marking (1, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 3), (2, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 3), (2, 3)]
Press Enter to continue:
Dequeueing
Current position: (2, 3)
Marking (2, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 3, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 3), (3, 3)]
Press Enter to continue:
Dequeueing
Current position: (2, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 3, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(3, 3), (3, 3)]
Press Enter to continue:
Dequeueing
Current position: (3, 3)
Goal reached at (3, 3)

```

# Answer
> 2 votes
Yes. There is no point having duplicates in the queue, so don't enqueue a position if (a) it has already been visited, or (b) it is already on the queue.

What happens if you skip checking whether it is already on the queue? Depending on how the rest of your code works, this could slow down your implementation significantly (it could increase the asymptotic running time from linear to quadratic).

---
Tags: search-algorithms, queues
---


# Question
Title: Algorithm to compose identity from a set of permutations
Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity permutation?

# Answer
> 4 votes
Assuming that "smallest composition" means smallest number of permutations used in the composition, then the NP-complete Pancake Flipping Problem is a special case of your problem.

# Answer
> 0 votes
$\mathcal{PRODUCT-PARTITION}$ is strongly $\mathrm{NP}$-hard as shown by Ng et al.

If you allow the representation of a permutation over $\mathbb{Z}^{\*}\_p$ to be almost-unary: except for one permutation, every other is given by the multiplier $a\in\mathbb{Z}^{\*}\_p$ in unary. And lastly, $p$ itself is given in binary. The only one other permutation is given by its multiplier $A\in\mathbb{Z}^{\*}\_p$ in binary, then your problem is $\mathrm{NP}$-hard.

Now, we show that $\mathcal{PRODUCT-PARTITION}$ can be reduced to our problem $\mathcal{PERM-IDENTITY}$.

**Theorem**: $\mathcal{PRODUCT-PARTITION}\leq\_p\mathcal{PERM-IDENTITY}$

**Proof**: Given an instance $\\{a\_1,\\:a\_2,\\:\dots,\\: a\_n\\}$ of $\mathcal{PRODUCT-PARTITION}$, we show how to construct an instance of $\mathcal{PERM-IDENTITY}$.

Since all the $a\_i$'s are given in unary (thanks to strong hardness), we are able to, in polynomial time, construct a prime $q$ (in unary) that is bigger any prime divisor of all the $a\_i$'s. By $\Pi$, we denote the product of all the $a\_i$'s. We can assume $\Pi$ to be a square number and that no $a\_i$ is equal to $1$. Taking the modulus to be some big enough $k$th power of $q$ such that $p=q^k\>\Pi$. All the following is done modulo $p$.

Now, we transform each $a\_i$ to a permutation $\pi\_i$ over $\\{0, 1, \dots, p-1\\}$ that describes the operation of multiplying with $a\_i$ over $\mathbb{Z}\_p$.

Now, the produced instance of our problem is $\\{\pi\_1, \\:\pi\_2, \\:\dots, \\:\pi\_n,\\:sqrt(\Pi)^{-1}\\}$ (modulo $p$) (actually, the last one should be the corresponding permutation of $sqrt(\Pi)^{-1}$, but abusing the notation a little bit may not be quite harmful here).

If the given $\mathcal{PRODUCT-PARTITION}$ instance is a $\mathrm{YES}$ instance, then by taking the set of permutations corresponding to the set of numbers in the solution to the $\mathcal{PRODUCT-PARTITION}$ instance and $sqrt(\Pi)^{-1}$, we can easily see that the produced instance is a $\mathrm{YES}$ instance of $\mathcal{PERM-IDENTITY}$.

Conversely, if the produced instance of $\mathcal{PERM-IDENTITY}$ is a $\mathrm{YES}$ instance, then note that the product of any subset of the $n$ permutations corresponding to $a\_i$ is quite small to $p$ (in the magnitude of their corresponding natural numbers). So, in order for the product to be $1\\:\mathrm{mod}\\:p$, the last permutation corresponding to $sqrt(\Pi)^{-1}$ (which is somehow bigger than the $a\_i$'s) must be taken. Then, the set of $a\_i$'s corresponding to the rest of the solution to the produced instance of $\mathcal{PERM-IDENTITY}$ problem must multiply up to exactly $sqrt(\Pi)$ (which is somehow similar in magnitude to the $a\_i$'s). Thus, the given $\mathcal{PRODUCT-PARTITION}$ instance is a $\mathrm{YES}$ instance.$\square$

---
Tags: algorithms, complexity-theory, combinatorics, permutations
---


title: Master theorem recurrence relation

text:
# Question
Title: Master theorem recurrence relation
Consider I have the following recurrence

$$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\\,.$$

Now, by the master theorem, if we evaluate $n^{\log\_{b}{a}}$, we get $n^{\log\_{b}{a}} = n^{\log\_{3}{10}} = n^{2.095}$. Now, can anyone please explain me, which of the three cases apply? If you plot these functions you can see that $n^2\log^5 n$ clearly dominates. So, the answer should be $\Theta(n^2\log^5n)$.

However, if you try plugging in values in this calculator, you see that the answer is $\Theta(n^{\log\_{3}{10}})$. Does anyone have a formal reason? I am still confused as to which of these conditions apply.

# Answer
> 2 votes
Plotting isn't foolproof: for any $k,\varepsilon\>0$, we have $\log^kn = o(n^\varepsilon)$ (here, I've cancelled the common term of $n^2$). However, you can need to take $n$ *really* big to see it when $\varepsilon$ is small (e.g., $0.095$) and $k$ isn't so small (e.g., $5$). Here's the plot for $0\leq n\leq 10^{131}$, again with the $n^2$ term cancelled, and it looks quite different from your plot up to $n=10^5\\,$!

Indeed, this question may even have been designed to catch you out if you try to compare the asymptotic growth by plotting instead of by understanding.

---
Tags: asymptotics, master-theorem
---


# Question
Title: NP-hardness of problem with indices and subsets
Consider the following problem.

> Let $S=\\{1,2,\dots,n\\}$, and $A\_{ij}\subseteq S$ for $i,j\in S$. Does there exist a *strict* subset $T\subset S$ such that for all $j\not\in T$, there exists $i\in T$ for which $T\subseteq A\_{ij}$?

(For $T=S$, this is trivially true, so we disallow it.)

The problem is in NP: given a set $T$, it is easy to verify whether it satisfies the property. Is it also NP-hard, or does there exist a polytime algorithm?

I tried to construct such a set $T$ greedily by starting with some $i\in S$. If $i\in A\_{ij}$ for all $j\not\in i$, we can choose $T=\\{i\\}$ and are done. Otherwise, there is some $j$ for which $i\not\in A\_{ij}$, so we can try adding $j$ into the set, and iterate on the new set $T=\\{ij\\}$ until the process stops. The problem is that there is no guarantee that this will stop before $T$ is the whole set $S$ even if such $T\neq S$ exists.

I also thought about dynamic programming, but it's not clear what the subproblems should be in this setting. On the NP-hardness side, I thought about reducing from some problems related to sets. There are problems like subset-sum or partition, but those concern sums of elements and are not directly relevant.

# Answer
> 1 votes
This question shows that Vašek Chvátal is a hero.

Reduce from graph kernel.

In the **GRAPH KERNEL** problem, the input data is a digraph and the task is to determine whether it has a kernel.

A kernel of a digraph is a subset $S$ of its vertex set which satisfies **(i)** no two vertices of $S$ are adjacent, and **(ii)** for every vertex not in $S$ there exists an arc from some vertex in $S$ pointing to it.

So, we need to transform a digraph to your **set matrix** problem.

For each original vertex, create an element. Call these elements vertex-elements. Denote this set of element by $V$.

For each original arc, create an element. Call these elements arc-elements.

Now, to ensure $T$ is an independent set in this digraph. For each arc-element $a=(u,v)$, set $A\[u,a\]=V\setminus\\{v\\}$ and $A\[v,a\]=V\setminus\\{u\\}$. Also, just in case none of $u$ and $v$ is included in $T$, for every $w\neq u, v$, set $A\[w,a\]=V\setminus\\{u,v\\}$.

To ensure $T$ is a dominating set in a digraph, for each arc $a=(u,v)$ set $A\[u,v\]=V$

All the other entries of $A$ are set to $\emptyset$.

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


# Question
Title: Proof of a greedy algorithm concerning “Buy and Resell Problem”
"Buy and Resell Problem" can be described in the following way:

There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from city 1 to city $n$, one by one. When reaching a city, he can buy exactly one product with the price in this city, or sell exactly one product if he currectly has at least one product. He can also do nothing and then go on to the next city. The problem is how to plan a strategy so that he can earn maximal money. He has unlimited money initially.

For example, if $n=5$ and the prices are 3,2,5,1,4, then the maximal profit he can earn is $5-2+4-1=6$.

There is a correct greedy algorithm to this problem. When reaching city $i$, consider all $j$ in $1 ... i-1$, and find a $j$ with lowest price such that he doesn't buy a product in city $j$ (he could have sold a product in city $j$). If such $j$ does not exists or the price of city $j$ is higher than city $i$, he simply does nothing in city $i$. Otherwise he buys a product in city $j$ and sells it in city $i$. If he has sold a product in city $j$, it means he does nothing in city $j$ after finishing the $i$th city. The algorithm runs all $i$ in increasing order, and finally gives the best strategy.

The pseudo-code can be written as:

```
maintain a set s which is empty initially
maintain a boolean array named sell whose items are false initially
profit = 0
for i in 1 to n
  if s is not empty
    select an item j in s with the loweset price
    if price_j is lower than price_i
      profit += price_i - price_j
      if sell_j == true
        sell_j = false
      else
        erase item j from set s
      endif
      sell_i = true
    endif
  endif
  insert i to set s
endfor
output profit

```

The solution is quite simple and can be easily implemented using a priority\_queue, which takes $\Theta(n \log n)$ time in total, but how to prove its correctness?

# Answer
> 3 votes
*Summary: It is proposed to label the simple and intriguing algorithm given in the question as **Adaptive Greedy**. Several characterizations of the best strategy are presented. Also included is a rigorous and nontrivial proof of the algorithm. Some interesting original exercises and topics are attached.*

---

## Reformulation in mathematical terms

Let $a..b$ stand for the integers from a to b inclusively.

Let us fix $n\ge 2$ and $p(i)\>0$, the price of an item in city $i \in 1..n$ (All items are the same except their prices). **Assume all prices are different.** This assumption is not necessary in order to establish the arguments, the concepts and conclusions below. However, it does simplify them significantly. For example, the algorithm becomes deterministic, producing the same output given the same input.

**A strategy $s$** is a function from $1..n$ to $\\{1,0,-1\\}$, where $1,0$ and $-1$ mean buying, passing and selling respectively.

Given a strategy $s$, let $h\_s(i)=\sum\_{j\in 1..i}s(j)$ be the number of items held right after city $i$ and also let $h\_s(0)=0$. A strategy is **an admissible strategy** if $h\_s(i)\ge0$ for all $i$; otherwise it is an inadmissible strategy. We will only consider admissible strategy unless stated otherwise.

The profit made by strategy $s$ is profit$(s)=\sum\_{i\in 1..n} -s(i)p(i)$. If strategy $m$ makes the maximal profit, that is, profit$(m)=\max\_s($profit$(s))$, then we say $m$ is **a best strategy**. Since there are finitely many strategies, there must exist at least one best strategy.

---

## The adaptive greedy algorithm that returns the best strategy

Here is the pseudocode in Python style for the adaptive greedy algorithm. It is the same as the pseudocode in the question except that it uses the self-explanatory terms defined above and that it returns the best strategy instead of the maximal profit. We will prove that it returns the unique best strategy shortly.

```
Input:
  price $p(i)$ for $i\in 1..n$.
Procedure:
  Let s be the all-passing strategy, i.e., s(i)=0 for i in 1..n
  For each city from 1 to n:
    Try finding the previous city where s passes or sells with the \
       lowest prices that is lower than the price at the current city.
    If found, let s sell in the current city and change its action \
       at the city found from pass to buy or from sell to pass.
Output:
    strategy s

```

The above algorithm, or its equivalent version given in the question, will be referred to as "this algorithm".

---

## Is this algorithm a greedy algorithm and why is it better called adaptive greedy?

At each city, given all admissible pairs of choices of an action in the current city and a change of the action in a previous city, this algorithm selects the pair of choices that can increase the profit the most if it is possible to increase the profit. Otherwise, this algorithm does nothing. **That locally optimal selection of admissible choices at each successive city is why we call this algorithm greedy.**

Readers might wonder why I explain this algorithm can be classified as greedy, a fact that seems obvious and is assumed by the questioner. That classification is, in fact, not conclusive at all. In fact, the Wikipedia entry on greedy algorithm says the following.

> Greedy choice property
> We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, **a greedy algorithm never reconsiders its choices**.
>
> Optimal substructure
> "A problem exhibits optimal substructure if **an optimal solution to the problem contains optimal solutions to the sub-problems**."\[2\]

Note that this algorithm reconsiders all of its choices made so far when it makes every new choices. When this algorithm runs for cities 1, 2, 3, 4, 5 with prices 1, 2, 3, 4, 5 respectively, the unique optimal solution returned by it, buying in city 1 and 2 and selling in city 4 and 5, does not contain any optimal solution to any sub-problem it has considered except for two cities. It is clear this algorithm is **not an ordinary greedy algorithm**. Nor does it belong to dynamical programming in its usual sense. Readers can also check some answers to does every greedy algorithm have matroid structure.

Considering the definition and explanations in the Wikipedia, I propose to **label this algorithm as an adaptive greedy algorithm, a greedy algorithm in the more general sense of "greedy"**. More precise definitions of adaptive greedy algorithm will be referenced here after they become available elsewhere.

Henceforth, this algorithm will also be referred as "this greedy algorithm" or "this adaptive greedy algorithm".

---

## Why is it not easy to prove this greedy algorithm is correct?

All greedy algorithms other than this algorithm I have seen so far build larger optimal solutions by keeping the smaller optimal solutions intact and adding one more element. Their correctness are often proved by one of the following three strategies, which are not necessarily mutually exclusive.

* "**Staying Ahead**". Show that after each step of $G$, its solution is at least as good as any other algorithm's.
This proof technique applies to Dijkstra's algorithm that finds the shortest path between nodes in a graph and the algorithm that always selects next interval of earliest ending time to find the most compatible interval in activity selction problem (which is also a kind of interval scheduling).
* "**Unimprovable Solutions**". Give any other solution, we can gradually improved it until it becomes unimprovable. Show all unimprovable solutions give the same result or there is only one unimprovable solution. Show that the solution found by greedy algorithm is unimprovable.
This proof technique applies to the usual greedy algorithms for problems such as Interval Scheduling for Minimal Maximum Lateness and others \[1\] \[2\] \[3\] \[4\] \[5\].
* "**Always promising**". If $G$ is a weighted matroid or greedoid, its standard greedy algorithm adds one more element to the current result subset in each stage, always promising there is a desired subset with maximal total weight that contains the result subset so far. When the algorithm ends, that promised desired subset will become none other than the result subset. The way to keep the promise is to use exchange of elements. This proof technique applies to most of problems tagged with "greedy algorithm" including Kruskal’s algorithm or Prim's algorithm for minimal spanning tree.

However, as observed before, the new decision made by this algorithm at each city may, more often than not, modify the decisions for previous cities. In fact, the decision made at the last city may modify the selected action of the first city that has stayed the same for all previous partial solutions. This modification makes it non-trivial to prove the correctness of this simple algorithm. I encourage interested readers to try proving it. Any proof that is easier than the proof below will be a nice surprise.

In fact, there is **not a single proof of the correctness of this algorithm** as far as I have searched. Many answers, articles or online programming contests may explain clearly the greediness (in its plain sense as in English) of this algorithm or provide vast numerical evidences, which are still, however, far from a rigorous proof of its correctness.

It turns out only the second proof strategy, "unimprovable solutions" can be applied to this adaptive greedy algorithm successfully, as shown in a later section of this answer. There is a new twist, though. The uniqueness of the unimprovable solution can only be established by induction with the help of applying this algorithm. I am stilling searching for ways to show that uniqueness directly without using this algorithm.

---

## The characterization theorem on the best strategy

An increasing integer pair $(i,j)$ is said to be **$s$-clearance-separated** if $h\_s(z)=0$ for some $z\in i..(j-1)$.

A strategy $s$ to be said to **improvable at two selected cities** if the following conditions hold.

* (room to improve) $s$ buy or pass at a lower price in one city but buy or pass at a higher price in the other city. Assume the former city is city $i$ and the other city is city $j$.
* (no obstruction to switch) $i\>j$ or $i\<j$ and $(i,j)$ is not $s$-clearance-separated.

A strategy $s$ is **unimprovable** if $h\_n(s)=0$ and it is not improvable at any two cities.

(**The characterization theorem**) The following four propositions about a strategy $s$ are equivalent.

1. (**best strategy**) $s$ is a best strategy.
2. (**unimprovable strategy**) $s$ is unimprovable.
3. (**output of the greedy algorithm**) $s$ is the unique strategy produced by this adaptive greedy algorithm.
4. (**anatomy of the best strategy**) There are integers $0=i\_0\lt i\_1\lt i\_2\lt\cdots \lt i\_t=n$ such that $h\_s(i)=0$ if $i=i\_j$ for some $j$ and $h\_s(i)\gt0$ otherwise. That is, $i\_j$'s are all clearance cities where he ends up with no item in his inventory. Call cities $(i\_{k-1}+1)..i\_k$ of term $k$.
    * If $s$ buys in a city of some term and sells in a city of the same term or a previous term, the buying price is smaller than the selling price.
    * If $s$ buys in a city of some term and passes in a city of the same term or a previous term, the buying price is smaller than the passing price.
    * If $s$ passes in a city of some term and sells in a city of the same term or a previous term, the passing price is smaller than the selling price.
    * Each passing price happens in a city of a different term.
    * All passing prices form a decreasing sequence.

---

## Proof of the theorem

**"best strategy $\Rightarrow$ unimprovable strategy"**: Suppose strategy $s$ is not unimprovable.

If $h\_s(n)\>0$, then we can find city $b$, the last city where $s$ buys. Construct $s'$, the strategy that is the same as $s$ except $s'$ passes in city $b$. Since $h\_{s'}(i)=h\_s(i)$ if $i\lt b$ and $h\_{s'}(i)=h\_s(i)-1\ge h\_s(n)-1\ge 0$, $s'$ is an admissible strategy. Since $\text{profit}(s')=\text{profit}(s)+p(b)$, $s'$ makes bigger profit than $s$.

If $h\_s(n)=0$, then we can find two integers $i,j\in 1..n$ such that $p(i)\<p(j)$ such that one of the following two cases happens.

* $s(i)=s(j)=0$ or $s(i)\<s(j)$. Furthermore, $i\<j$.

Let $s'$ be the strategy that is the same as $s$ except that $s'(i)=s(i)+1$ and $s'(j)=s(j)-1$. Since $h\_{s'}(t)\ge h\_s(t)$ for all $t$, $s'$ is an admissible strategy. We have, $$\text{profit}(s')-\text{profit}(s)=-p(i)+p(j)\gt0$$
* $s(i)=s(j)=0$ or $s(i)\>s(j)$. Furthermore, $i\<j$ and $(i,j)$ is not $s$-clearance-separated.

Recall that $h\_s(t)\ge0$ for all $t$ and, since $(i,j)$ is not $s$-clearance-separated, $h\_s(t)\ge1$ for all $t\in i..(j-1)$. Let $s'$ be the strategy that is the same as $s$ except that $s'(i)=s(i)-1$ and $s'(j)=s(j)+1$. Since $h\_{s'}(t)= h\_s(t)$ for all $t\not\in i..(j-1)$ and $h\_{s'}(t)= h\_s(t)-1$ for all $t\in i..(j-1)$, $h\_{s'}(t)\ge0$ for all $t$. That is, $s'$ is an admissible strategy. We have, $$\text{profit}(s')-\text{profit}(s)=p(i)-p(j)\gt0$$

So in all cases, we have found an admissible strategy that makes more profit then $s$.

**"unimprovable strategy $\Rightarrow$ output of the greedy algorithm"**: We will use mathematical induction on $n$.

The base case, $n=2$ is easy. In fact, we can extend the whole exposition to include the case when $n=1$, which becomes the obviously-true base case.

Suppose the implication is true for $n$ cities. Now consider the case of $n+1$ cities. Let $w$ be an unimprovable strategy on $1..(n+1)$ for some price function $q$. Since $w(n+1)=h\_w(n+1)-h\_w(n)=-h\_w(n)\le 0$, there are two cases.

* $w(n+1)=0$. That means, $h\_w(n)=0$. Let $s$ be the restriction of $w$ to $1..n$. Then $s$ is an unimprovable strategy on $1..n$ for the same prices as $q$. Then $s$ is the uniqued strategy produced by the greedy algorithm running up to city $n$. If we continue to run the greedy algorithm at city $n+1$, it must choose to passes in that last city since $w$ is unimprovable. That is, the greedy algorithm will produce $w$.
* $w(n+1)=-1$. That means, $n+1$ is a clearance city where $w$ sells. Treating 0 as an clearance city if necessary, let $c$ be the last clearance city before $n+1$. Let $k$ be the city among $(c+1)..n$ where $w$ passes or buys with the highest price. Let $s$ be the strategy on $1..n$ that is the same as $w$ except that $s(k)=w(k)-1$. Then we can verify that $s$ is an unimprovable strategy on $1..n$ for the same prices as $q$. Then $s$ is the unique strategy produced by the algorithm running up to city $n$. If we continue to run the algorithm at city $n+1$, we can verify that it will select to sell in that city as well as change the action in city $k$ from $s(k)$ to $w(k)$. That is, the greedy algorithm will produce $w$. (There are quite some details left out in this part of the proof. Interested readers may take a look at Exercise 0.)

So, we have shown the implication is also true for $n+1$.

**"output of the greedy algorithm $\Rightarrow$ best strategy"** Let $s$ be the unique strategy generated by the greedy algorithm. Let $b$ be a best strategy. Then $b$ must be an unimprovable strategy and, then, must also be the unique strategy generated by the greedy algorithm as we just proved.

**"unimprovable strategy $\Leftrightarrow$ anatomy of the best strategy"**. The latter one is basically a careful refinement of the former one into cases.

---

## Beyond this problem

There are multiple variations and possible generalizations. It should be a nice topic for an undergraduate student or a master student to look further into this phenomenon, since this adaptive greedy algorithm does not fit into the framework of matroid or greedoid.

Please leave a comment if anyone wants to collaborate on this topic. Please leave a comment if anyone encounters some literature that looks like applicable, especially in integer linear programming theory or generalized greedoid or submodular functions.

---

## Some exercises and topics

The answers to all the exercises are known. However, topics are much harder, to which I do not claim to know an answer or verify the answer.

**Exercise 0.** Fill the missing details in the proof of "unimprovable strategy $\Rightarrow$ output of the greedy algorithm". As a hint, "anatomy of the best strategy" may help you get a better understanding of the cities in the last term. (Thanks to user zbh2047, the questioner, who points out a missing case in a previous more-complex formulation of "unimprovable strategy")

**Exercise 1.** Suppose the prices in different cities can be the same. Then there might be multiple best strategies. Show that the algorithm, after slight modification, is able to find all best strategies.

**Exercise 2.** By switching buying and selling, describe a greedy algorithm that starts from city $n$, moving backwards. Prove its correctness.

**Exercise 3.** Suppose he can only either buy an item or sell one item in each city. That is, he cannot do nothing in any city. Describe a greedy algorithm to find the strategy that makes the most profit or, if no profit can be made, make the least loss. Prove its correctness.

**Exercise 4.** Describe a greedy algorithm that, in each iteration, tries determining the available city of lowest price to buy an item and the corresponding available city with the highest price that is higher than that lowest price to sell an item, staying away from the inadmissible strategies. If it can find the corresponding city, mark both cities as unavailable; otherwise, mark the first city as unavailable. Prove its correctness.

**Exercise 5.** Can you find a greedy algorithm and prove its correctness in each of the following situations?
(Part a) Suppose he can short items. That is, the number of items hold by him can be as low as $-n$ but not any lower for some positive integer $n$.
(Part b) Suppose for some positive integer $k$, if the number of items held by him is no more than $k$ in the last city, then the total prices of those items will be added to his profit.
(Part c) Suppose he is required to buy in some specified cities and to sell in some other specified cities.

**Exercise 6.** Show that the best strategy can be verified in linear time of $n$. The characterization theorem on the best strategy tell us that the best strategy only depends on the relative size of the prices. Show that the minimal number of comparisons needed to determine the best strategy for 2, 3, 4, and n cities are 1, 3, 5 and $\Theta(n\log n)$ respectively.

**Topic 1.** Suppose he can only buy or pass initially until he holds $k$ items for some positive integer $k$. Then he can buy or sell one item or pass as before. (When) is there a greedy algorithm?

**Topic 2.** Suppose there is a selling cost $t(i)\>0$ associated to sell in city $i$ for each $i\in 1..n$. (When) is there a greedy algorithm?

**Topic 3.** Let $c(n)$ be the minimal number of comparisons needed to sort any $n$ numbers and $z(n)$ be the minimal number of comparisons needed to find a best strategy for any prices in $n$ cities. We know $z(n) \le c(n)$. Is it true that $c(n)=z(n)$ for all $n$?

All above exercises and topics are created by this author except exercise 4 that comes from an answer at Quora

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


# Question
Title: Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?

I would not expect this would work over an alphabet of size two or more, since it is PSPACE-complete to check whether a regular expression is universal. However, since regular languages over unary alphabets have nice characterizations, I would expect there would be some way to check the universality of an NFA over an unary alphabet.

# Answer
Determining whether a unary NFA is universal is coNP-complete, as proved by Stockmeyer and Meyer, Word Problems Requiring Exponential Time. See Gruber and Holzer, Computational Complexity of NFA Minimization for Finite and Unary Languages, for more results in this vein.
> 4 votes

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


title: Understanding SLDNF-forest

text:
# Question
Title: Understanding SLDNF-forest
I am trying to understand this program and the respective forest. This is from the book Logic,Programming and Prolog by Ulf Nilsson.

Question:

* In the main tree, why from ←off\_gound(a) can you derive ⧠ ?
* In the main tree, why was chosed on(b,a) first instead of on(c,b)?

Could someone please explain this?

Thank you so much in advance.

# Answer
To answer your first question: SLDNF resolution employs *negation as failure* to deal with negation.

So from ←$\neg$off\_ground(a) we derive ⧠ by trying to derive ←off\_ground(a) and failing (i.e. deriving **FF**). This is done in the upper tree on the right hand side.
> 1 votes

---
Tags: logic, programming-languages, trees
---


# Question
Title: About a pre-processing step for primal-dual weighted set cover problem
I was reading the paper titled "Primal-dual RNC approximation algorithms" by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.

They present a dual fitting based algorithm for weighted set cover. First let me set up the required concept to clarify where I am having trouble. Suppose we have $n$ elements ($U$) and $m$ sets ($S$). Each set has a positive weight. Let $E\_v$ holds the sets in which the element $v$ is present. Let $\beta =$max$\_{v \in U}$ min$\_{s \in E\_v}$ weight(s). Let also $IP^\*$ is the weight of an optimal set cover. It is easy to see, $IP^\*\geq \beta$.

Now assume we have an approximation algorithm for weighted set cover. What the paper is saying in the lemma is that you can do a pre-processing before starting the approximation algorithm as follows. You can scan through the sets and add any sets that have weight $\leq \beta/n$. Since there are $n$ elements the additional cost is at most $\beta$. Then they claim that

> Since $\beta$ is a lower bound on $IP^\*$, this cost is subsumed in the approximation. And this is the statement I did not understand.

# Answer
> 1 votes
The goal is to give an $O(\log n)$ approximation algorithm, starting with an algorithm that is already an $O(\log n)$ approximation algorithm, and optimizing it further. Adding the low cost elements results in an approximation ratio of $1 + O(\log n) = O(\log n)$, since the total weight of sets we add is $\beta$, which is also an upper bound on the value of the optimal solution.

---
Tags: approximation, set-cover
---


# Question
Title: Monte-Carlo Algorithm for counting 'on' bits in a binary array
Given a Monte-Carlo algorithm (called A) that given a binary array with b 'on' bits (one-bits) returns a, where in a probability of 1/2: $\frac b 3 \leq a \leq 3b$

How can I use A to build an algorithm that does the same, but with probability $poly(\frac 1 n)$ of success (success means $\frac b 3 \leq a \leq 3b$ ), using A? if A runs in $O(T(n))$ time ($T(n)$ is much smaller than $n$), what's the runtime of the new algorithm?

# Answer
> 1 votes
This is a standard technique. Run the algorithm multiple times and take the median answer. The median will be a success unless there are many failures; use a Chernoff bound to show that this many failures has the low probability you require. Typically, a constant number of runs will give a constant (but better than $1/2$) failure probability, poly-log runs will give polynomially small failure probability and a polynomial number of runs will give exponentially small failure probability.

---
Tags: algorithms, randomized-algorithms
---


title: Asymptotic bound of a heap's height

text:
# Question
Title: Asymptotic bound of a heap's height
Today I was taught that since the height of a heap cannot exceed $\log n$, it is $O(\log n)$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. That is fine, but I think we should further specify it as $\Theta(\log n)$ since it, at that same time, must be greater than $\log n - 1$, and hence also fits $\Omega(\log n)$. I suggested this after class, but I was repeatedly told that $O(\log n)$ was correct, and the correctness of $\Theta(\log n)$ was not explicitly confirmed.

Is $\Theta(\log n)$ correct? If so is there a common reason / justification to just use $O$ instead, and possibly even to avoid using $\Theta$?

Clarification: it's a binary heap.

# Answer
Yes $\Theta(logn)$ is correct. By the definition of $\Theta$ notation we can say that some function $g(n)$ is at least $k\_1⋅f(n)$ and also it is at most $k\_2⋅f(n)$ for considerably large $n$ and $k\_1 \> 0$ and $k\_2 \> 0$. If you apply this definition to the heap's height, you will find that the heap's height satisfies this. So, $\Theta(logn)$ is totally correct.
> 1 votes

---
Tags: data-structures, asymptotics, heaps
---


title: Order of given value in AVL tree

text:
# Question
Title: Order of given value in AVL tree
given an AVL tree with $size$ value to any vertex $v$ in the tree (which is the size of the tree rooted in $v$), is it possible to tell for a given value in the tree, what its order in the sorted group in $log (n)$ time complexity?

# Answer
Searching for the value in the tree is a $O(\log n)$ task.

Then, we can visit the path leading to the value, from the leaf (the value), to the root. At every intermediate node, we know how many other values there are further on the left: none, if we moved up from the left subtree, and `left.size` (which is assumed to be stored in each node) otherwise.

So, we can add all the relevant `size` values, counting up how many other values we have on the left of our value, so retrieving the order of the value in $O(\log n)$.
> 1 votes

---
Tags: data-structures
---


# Question
Title: $\mathrm{\oplus P^{BPP}\subseteq BPP^{\oplus P}}$
Toda showed long ago that $\mathrm{PH\subseteq BP.\oplus P\subseteq BPP^{\oplus P}}$. That somehow describes the power of Parity Non-deterministic Computation.

If we swap the base and the exponent of the relativized class $\mathrm{BPP^{\oplus P}}$ to obtain yet another relativized one, namely $\mathrm{\oplus P^{BPP}}$. Then what have we obtained? A bigger or a smaller class?

# Answer
> 0 votes
You get a smaller one, in words $\mathrm{{\oplus P}^{BPP}\subseteq BPP^{\oplus P}}$. Indeed, the stronger claim that $\mathrm{{\oplus P}^{BPP}\subseteq BPP^{\oplus P\[1\]}}$ also holds.

Consider a language $L\in \mathrm{{\oplus P}^{BPP}}$, by definition, there exists an oracular non-deterministic machine $N$ and a $\mathrm{BPP}$ machine $M$ such that: on a given input string $x\in \Sigma^\*$, we have that $x\in L$ if and only if $N^M(x)$ has an odd number of accepting paths.

Now, we may assume that by repetition and taking majority, the probability of $M$ to produce wrong answer is **exponentially small**.

The following language $\mathcal{O}$ is in $\oplus P$: on an input string $x\in\Sigma^\*$ and a polynomially long random bit string $r$ (i.e. input data is $(x,r)$), simulate $N^M(x)$ where the random coin tosses using *inside* the oracle calls to $M$ are taken from $r$ one by one from left to right; accept only when the number of accepting paths is odd.

So, on a given input string $x\in\Sigma^\*$, we guess a polynomially long random bit string $r$, call the oracle $L\in\oplus\mathrm{P}$ on input $(x, r)$and return the same answer.

Clearly, the probability that the random bit string $r$ makes $M$ produce wrong answer to *any* oracle call is extremely small. So, w.h.p the answer returned by the only one call to $\mathcal{O}$ is identical to the answer of $N^M(x)$.

Thus, $L\in\mathrm{BPP^{\oplus P\[1\]}}$. The claim that we obtain a smaller class holds.

---
Tags: complexity-theory
---


# Question
Title: Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$
My question is as follows: Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq \_T^p B$ nor $B \leq \_T^p A$, where $A \leq \_T^p B$ if there exists a polytime deterministic oracle machine that computes $A$ given access to $B$. That is, $A \leq \_T ^p B$ if $A = M^B$ for some Turing machine $M$. I am getting stuck right at the start of the proof.

We have previously shown that there exists $B \in NP$ such that it is not $NP$-complete nor in $P$ by setting up a set of requirements and using delayed diagonalization. Given an $NP$-complete language $A$, and an enumeration of oracle polytime Turing machines $\\{ M \_e \\}\_{e\in \mathbb{N}}$, the requirements were $$R\_{2e}: \exists y (A(y) \neq M\_e^B(y)) \\ R\_{2e + 1} : \exists y(B(y) \neq M\_e(y)).$$

I want to try a similar strategy to build $A$ and $B$ in $NP$, thus having requirements $$ R\_{2e} : \exists y (A(y) \neq M\_e^B(y)) \\ R\_{2e +1}: \exists y (B(y) \neq M\_e^A(y)) $$

I don't really know how to start the process in this case, or if this is even the right method here. I would be thankful for some advice on how to continue or on a better strategy. Thanks in advance!

# Answer
> 3 votes
There is a well-known classical result of the theory of $p$-degrees stating that every non-zero $p$-T-degree splits into two incomparable $p$-T-degrees.

So assuming $P\neq NP$, by the splitting theorem, the $p$-T-degree of Turing-complete problem for $NP$ splits into two non-T-complete incomparable $p$-T-degrees.

**REFERENCES**

Sublattices of the polynomial time degrees

LADNER, R. E. (1973), **Polynomial time reducibility**, in Proc. 5th Annual ACM Sympos. on Theory of Comput., pp. 122-129

LADNER, R. E. (1975), **On the structure of polynomial time reducibility**, J. Assoc. Comput. Math. 22, 155-171

---
Tags: complexity-theory, turing-machines, np-intermediate
---


# Question
Title: Number of IEEE 754 doubles between two adjacent single-precision floats
Between an adjacent pair of nonzero IEEE single precision real numbers, how many IEEE double precision numbers are there?

I was also wondering if this question has something to do with the hidden bit.

Can anyone help me?

# Answer
> 1 votes
Let's consider two made-up number systems: 2-dec and 3-dec. In 2-dec, numbers are specified to two decimal points (in decimal). In 3-dec, it's three. Between, say, 1.2 and 1.3, which are adjacent in 2-dec, we have 1.21, 1.22, 1.23, 1.24, 1.25, 1.26, 1.27, 1.28, 1.29 in 3-dec.

Hope this helps.

As an aside, the answer might potentially depend on whether the numbers are denormalized or not.

---
Tags: floating-point
---


title: What's the output of this algorithm?

text:
# Question
Title: What's the output of this algorithm?
Given the question below:

*Consider that, on the procedure below, the variable X is defined globally and the parameters of the vr function are passed by value*

```
procedure vr(u,v) {
   u = 2*u;
   x = u+v;
   u = u - 1;
}

```

**Define the value of x in the end of the following:**

```
x = 4;
y = 2;
vr(x,y);
print(x);

```

I always knew that parameters passed by value were actually a copy of the original value, but in this case i can't tell what scope is being used for the function.

I also would like to read more about cases like that. If you can, please leave any suggestive material so i can get more in depth of this subject.

I know that this is a very bad practice of naming variables and should be avoided, but in this case i guess it was intentional for the problem.

# Answer
You can unroll the procedure:

```
x = 4;
y = 2;
u = x;
v = y;
u = 2*u;
x = u+v;
u = u-1;
print x;

```

This is semantically equivalent to your program.

Once you copy the value of `x` to `u`, the link between the two disappears. This is in contrast to *references* in C++ or *mutable objects* in python, which are really pointers; if `u` were a reference (i.e., if parameters were passed by reference), then the assignment `u = x` would have *identified* the two variables as pointing at the same location in memory. As it is, `u` is just a value (since parameters are passed by value), and so this linkage is absent.
> 1 votes

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


# Question
Title: Is this a correct way to show that a problem is coNP-complete?
Let $A$ be a problem that I want to show it is **coNP-complete**. I know I could just show its complement $\bar{A}$ is NP-complete or that $\bar{A}$ is in NP and for some coNP-complete problem $Q$, show that $Q$ can be **Karp-reduced** to $A$.

But I wonder if the following steps are sufficient to show that **A** is **coNP-complete**?

1. Show that $A$ is in $coNP$ by showing that its complement is in NP
2. Choose one **coNP-complete** problem $Q$ and **Cook-reduce** it to $A$.

Does the coNP-complete class still be distinguishable (under the assumption $P\neq NP$) from the NP-complete class? since it seems that any coNP-complete problem is Turing-polynomially equivalent to any other NP-Complete problem.

# Answer
No, the steps are insufficient. You need to use a Karp reduction, since that's the type of reduction used in the definition of coNP-completeness.

SAT is NP-complete, but probably not coNP-complete (unless NP=coNP); and coSAT is coNP-complete, but probably not NP-complete. This distinction would be lost if you used Cook reductions.

Some questions on this site which are relevant are this one and that one, as well as a few others.
> 2 votes

---
Tags: complexity-theory, np-complete, np, decision-problem, co-np
---


# Question
Title: Pancake Sorting Graph Recursive Definition
I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n\>= 4. I can see obviously that, in the case of n=4, there will be 4 rough copies of the graph where n=3 with additions of 4 in certain places (where, and how is this defined?). But these copies aren't exact, and I can't find any detail on Wikipedia except for that it is indeed recursively defined. I'm asking with a view possibly to be able to generate a graph algorithmically for n\>=4 recursively.

Here is a graph for n=4 (so there are 4! / 24 possible configurations of pancakes, and thus 24 nodes in the graph). Here it is for n=4, on this Wikipedia article: https://en.wikipedia.org/wiki/Pancake\_graph.

See this Wikipedia article for more on Pancake Sorting - https://en.wikipedia.org/wiki/Pancake\_sorting.

# Answer
> 1 votes
From Wikipedia:

> The pancake graph $P\_n$ or $n$-pancake graph is a graph whose vertices are the permutations of $n$ symbols from 1 to $n$ and its edges are given between permutations transitive by prefix reversals.

$P\_n$ can be constructed from $n$ copies of $P\_{n-1}$. We can construct $P\_4$ from $P\_3$, which looks like:

We start by making 4 copies of $P\_3$ and numbering them 1 through $n$. Let's look at one particular copy and call it copy $i$. For each node in that instance of $P\_{n-1}$, replace $i$ with $n$ and then append $i$ to the end of each sequence. For the $n$th copy, we don't have to do any replacing and can simply append $n$ to the end.

For example, for the 2nd copy of $P\_3$ we'll first replace all the 2s with 4s and then append 2 to the end:

We now have a graph with nodes for all of the permutations of the elements from 1 to 4, and we have edges between sequences that can be transformed into one another by flipping a proper prefix. Edges from $P\_{n-1}$ are still valid in $P\_n$ because the only thing we've done is relabel and append a suffix.

Now go through each node and add a new edge going to the node corresponding to flipping the entire sequence. For example, (4,3,1,2) gets connected to (2,1,3,4), (1,2,3,4) gets connected to (4,3,2,1), etc.

The final graph for $P\_4$ as shown in the Wikipedia article linked in the question looks like:

# Answer
> 0 votes
> I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n\>= 4. ... I'm asking with a view possibly to be able to generate a graph algorithmically for n\>=4 recursively.

A webpage providing source code for pancake sorting in over 50 different languages is here: "Sorting algorithms/Pancake sort" at the Rosetta Code website.

See the paper: "Some relations on prefix reversal generators of the symmetric and hyperoctahedral group" (Jun 7 2018), by Saúl A. Blanco and Charles Buehrle:

> Page 1: "The best upper and lower bound known today for the general case appeared in `[5]` and `[12]`, respectively. Combined, one has that
>
> $$15 \left \lfloor \frac{n}{14} \right \rfloor \le f(n) \le \frac{18n}{11} + O(1).$$
>
> Computing the pancake number for a given n is a complicated task. To our knowledge, the exact value of f(n) is only known for 1 ≤ n ≤ 19 (see `[2, 6, 7, 12, 18]`). In fact, determining the minimum number needed to sort a stack of pancakes is an NP-hard problem \[\], though 2-approximation algorithms exists \[10\].
>
> `[2]` Shogo Asai, Yuusuke Kounoike, Yuji Shinano, and Keiichi Kaneko. Computing the Diameter of 17-Pancake Graph Using a PC Cluster, pages 1114–1124. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
>
> `[4]` Laurent Bulteau, Guillaume Fertin, and Irena Rusu. Pancake flipping is hard. J. Comput. System Sci., 81(8):1556–1574, 2015.
>
> `[5]` B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough, and W. Voit. An (18/11)$n$ upper bound for sorting by prefix reversals. Theoret. Comput. Sci., 410(36):3372–3390, 2009.
>
> `[6]` Josef Cibulka. On average and highest number of flips in pancake sorting. Theoret. Comput. Sci., 412(8-10):822–834, 2011.
>
> `[7]` David S. Cohen and Manuel Blum. On the problem of sorting burnt pancakes. Discrete Appl. Math., 61(2):105–120, 1995.
>
> `[10]` Johannes Fischer and Simon W. Ginzinger. A 2-Approximation Algorithm for Sorting by Prefix Reversals, pages 415–425. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.
>
> `[12]` Mohammad H. Heydari and I. Hal Sudborough. On the diameter of the pancake network. J. Algorithms, 25(1):67–94, 1997.
>
> `[18]` Y. Kounoike, K. Kaneko, and Y. Shinano. Computing the diameters of 14- and 15-pancake graphs. In 8th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’05), Dec 2005.

The Rosetta Code C++ implementation is:

```
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

// pancake sort template (calls predicate to determine order)
template <typename BidIt, typename Pred>
void pancake_sort(BidIt first, BidIt last, Pred order)
{
    if (std::distance(first, last) < 2) return; // no sort needed

    for (; first != last; --last)
    {
        BidIt mid = std::max_element(first, last, order);
        if (mid == last - 1)
        {
            continue; // no flips needed
        }
        if (first != mid)
        {
            std::reverse(first, mid + 1); // flip element to front
        }
        std::reverse(first, last); // flip front to final position
    }
}

// pancake sort template (ascending order)
template <typename BidIt>
void pancake_sort(BidIt first, BidIt last)
{
    pancake_sort(first, last, std::less<typename std::iterator_traits<BidIt>::value_type>());
}

int main()
{
    std::vector<int> data;
    for (int i = 0; i < 20; ++i)
    {
        data.push_back(i); // generate test data
    }
    std::random_shuffle(data.begin(), data.end()); // scramble data

    std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    pancake_sort(data.begin(), data.end()); // ascending pancake sort

    std::copy(data.begin(), data.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

```

> Output:
>
> ```
> 4 10 11 15 14 16 17 1 6 9 3 7 19 2 0 12 5 18 13 8
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> ```

---
Tags: graphs, sorting, recursion
---


# Question
Title: Better way to formulate these constraints?
I have a binary variable $x\_{ijt}^k$ that is $1$ iff job $i$ is assigned to machine $j$ at time $t$ using processor $k$. I would like to express the following constraints:

* If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j'\neq j$.
* If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j$ at time $t'\neq t$ using processor $k'\neq k$.

In other words, both constraints say that once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine.

For the first constraint, I write it as $x\_{ijt}^k+x\_{ij't'}^{k'}\leq 1$, for all $i,j'\neq j, k, k',t,t'$.

For the second constraint, I write it as $x\_{ijt}^k+x\_{ijt'}^{k'}\leq 1$, for all $i,j, k\neq k',t\neq t'$.

Can I improve this formulation?

# Answer
> 2 votes
Here is a different way to formulate the situation, which is simpler conceptually and which might be implemented more easily, although the number of variables is still the same (which can be not reduced fundamentally, anyway).

"Once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine". It looks like it is assumed that a processor is attached to the same machine regardless of the job or time. That means there is only one degree of freedom about the variable $j$ and $k$.

Let us use a new index $p=(j,k)$ to denote a pair of machine and a processor on it. Let binary variable $x\_i^{pt}$ be $1$ iff job $i$ is assigned to processor $p$ at time $t$ (the index $t$ and $p$ is put together since they represent the resources). Then we can **express the constraints as a single inequality**, $$x\_i^{pt}+x\_i^{p't'}\leq 1\quad \text{ for all }p\neq p',t,t', i$$

In the actual programming, we can pack $j$ and $k$ side by side to form $p$ as the union structure in C/C++. For example, let $p$ be a 32-bit unsigned integer whose upper 16 bits is $j$ and whose lower 16 bits is $k$. We can also use a hash table with $p$ as keys and $(j,k)$ as values.

# Answer
> 1 votes
If your measure of "better" is number of variables or number of constraints, I don't believe it is possible to do better. You obviously can't use fewer variables as all of them are already defined; your formulation hasn't added any new variables. You have one inequality per constraint, so I don't see how you would expect to have fewer inequalities.

---
Tags: linear-programming, integer-programming
---


# Question
Title: how to derive the complexity of the randomization solution to the majority element problem
The randomization solution is from majority-element, and the corresponding complexity given confused me very much.

The complete procedure of calculating iterations give is : $$ \begin{split} EV(iter\_{prob}) & \le EV(iter\_{modif}) \\ & \le \lim\_{n\to\infty} \sum\_{i=1}^n i \times\frac{1}{2^i} \\ & =2 \end{split} $$

I wanna know how to derive $ \lim\_{n\to\infty} \sum\_{i=1}^n i \times\frac{1}{2^i} $, and what does it stand for.

# Answer
> 2 votes
Given an array of length $n$, which is promised to have an element $x$ which appears more than $n/2$ times, the goal is to find $x$. Note that $x$ is unique.

The randomized solution goes as follows:

* Choose a random element $y$.
* Check whether $y$ appears more than $n/2$ times, in time $O(n)$.
* If so, return $y$.
* Otherwise, go back to the first step.

Since $x$ occurs more than $n/2$ times, the probability to select it is more than $1/2$. Hence the probability that we didn't choose it in the first $t$ attempts is less than $2^t$.

In order to calculate the expected time complexity, let us calculate the expect number of attempts until $y = x$; the expected time complexity would be that multiplied by $O(n)$.

Let $E\_t$ denote the event the we got to the $t$th round, that is, that the first $t-1$ attempts did not result in choosing $y = x$. Let $X\_t$ be the indicator variable for $E\_t$. The number of rounds is thus $X = \sum\_{t=1}^\infty X\_t$. Linearity of expectation shows that $$ \mathbb{E}\[X\] = \sum\_{t=1}^\infty \mathbb{E}\[X\_t\] = \sum\_{t=1}^\infty \Pr\[E\_t\]. $$ We get to the $t$th round if we failed to find $x$ in the first $t-1$ rounds, so $\Pr\[E\_t\] \< 2^{-(t-1)}$. Therefore $$ \mathbb{E}\[X\] \< \sum\_{t=1}^\infty 2^{-(t-1)} = \sum\_{t=0}^\infty 2^{-t} = 2, $$ using the formula for the sum of a geometric series. We conclude that the expected running time of the algorithm is at most $2 \cdot O(n) = O(n)$.

---

Another way to compute $\mathbb{E}\[X\]$ is using geometric random variables. Suppose that $x$ appears in $pn$ of the elements; so $p \> 1/2$. The random variables $X$ has distribution $G(p)$, that is, geometric with success probability $p$, and so $$ \mathbb{E}\[X\] = \frac{1}{1-p} \< \frac{1}{1-1/2} = 2. $$

A more sophisticated way to express this is that $X$ is stochastically dominated by a $G(1/2)$ random variable, and so $\mathbb{E}\[X\] \leq \mathbb{E}\[G(1/2)\] = 2$.

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


# Question
Title: Assuming NP≠coNP, do we have a similar theorem to Ladner's?
We have that $\mathrm{NP\neq coNP\iff NP\neq NP\cap coNP}$.

So by assuming that $\mathrm{NP\neq coNP}$, can we prove the existence of intermediate problem between $\mathrm{NP}$-complete and $\mathrm{NP\cap coNP}$?

# Answer
> 1 votes
**Yes**.

Before answering your question, let me make it clear that the reasoning provided in the link Filmus suggests above will not work for $\mathrm{NP\cap coNP}$, since this nasty class refuses to be efficiently enumerated. Also, it is very unclear to talk about $\mathrm{FP^{NP\cap coNP}}$-reductions, not to mention how to enumerate them. **Very faint an idea to do complexity theory that way**.

By Ladner's splitting theorem for $p$-degrees, every non-zero $p$-degrees splits into two lesser incomparable $p$-degrees.

Now, by the assumption that $NP\neq NP\cap coNP$, the $NP$-complete degree is separated from $P$ (zero $p$-degree). Applying the splitting theorem and downward closure for $p$-m-reduction of $NP$, we have that the complete degree $\mathcal{C}$ splits to two lesser degrees $\mathcal{A}$ and $\mathcal{B}$.

Whenever $\mathcal{C}$ splits into $\mathcal{A}$ and $\mathcal{B}$, we have that $\mathcal{C\subseteq P^{A, B}}$. And, we know that $\mathrm{P^{NP\cap coNP}=NP\cap coNP}$.

So, at least $\mathcal{A}$ or $\mathcal{B}$ must be outside of $NP\cap coNP$. That is the **intermediate degree** you are seeking.

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


# Question
Title: Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?
In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph G and a designated subset C of G’s nodes, is it possible to convert G to a directed graph by assigning directions to each of its edges so that every node in C has indegree 0 or outdegree 0, and every other node in G has indegree at least 1?

I need an idea how to prove it

# Answer
> 1 votes
take $C=\emptyset$ then you want to direct the graph so all node have in degree at least 1($DA1$) and now think about directed Hamiltonian cycle($DHC$) how you can reduce $DHC$ to $DA1$ !

# Answer
> 0 votes
Hint: Each edge has two possible orientations in the result. So you can encode this decision with a propositional variable. Next, encode your requirements for nodes in $C$ and outside $C$ as clauses. How many clauses do you need for that?

# Answer
> 0 votes
Our problem is $NP$-complete by a reduction from $3SAT$.

For each literal either positive or negative, create a vertex for it.

Set $C$ to be the set of literals themselves.

For each pair of literals of the same variable $x\_i$, namely $x\_i$ and $\lnot x\_i$, connect them by an edge. This ensures that whenever $x\_i$ is assigned to $\mathrm{TRUE}$ (all outgoing arcs) then $\lnot x\_i$ is assigned to $\mathrm{FALSE}$ (all incoming arcs), and vice versa whenever $\lnot x\_i$ is assigned to $\mathrm{TRUE}$ (all outgoing) then $x\_i$ is assigned to $\mathrm{FALSE}$ (all incoming). Hence, make sure the assignment is consistent.

Now, we take care of the clauses.

For each clause, create for it a new vertex. Connect this new clause-vertex to its $3$ literal-vertices in $C$. And so, we are done.

A satisfying assignment exists if and only the produced undirected graph can be oriented such that each vertex in $C$ is either a source vertex, i.e. $\mathrm{TRUE}$ with all outgoing arcs, or a sink vertex, i.e. $\mathrm{FALSE}$ with all incoming arcs. A clause-vertex needs to have at least one satisfying literal which is witnessed by the direction of an incoming arc. **DONE**.

---
Tags: complexity-theory, graphs, np-complete, np-hard
---


title: Hoare partitioning scheme in Quicksort

text:
# Question
Title: Hoare partitioning scheme in Quicksort
I'm reading about Quicksort algorithm, specifically using the Hoare partitioning scheme.

Wikipedia page says, that when choosing a pivot element one can use both `hi` and `lo` indexes. However, when implementing the same code in Python, my code fails in a very specific circumstances. My python code is a translation of the pseudo-code from Wikipedia.

```
def swap(A, i, j):
   A[i], A[j] = A[j], A[i]

def quick_sort_hoare(A, lo, hi):
    if lo < hi:
        p = hoare_part(A, lo, hi)
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)

def hoare_part(A, lo, hi):
    i = lo - 1
    j = hi + 1

    pivot = A[lo]

    while True:
        while True:
            i += 1
            if A[i] >= pivot:
                break

        while True:
            j -= 1
            if A[j] <= pivot:
                break

        if i >= j:
            return j

        swap(A, i, j)

```

This particular code works for many-many test-cases generated at random. However if I put `pivot = A[hi]` in partitioning, sometimes it fails. Specifically, when the last element(i.e. pviot) appears to be the largest in the array at hand. In that case `i` appears to be equal the length of the array and everything goes to the infinite recursion.

Furthermore, in Introduction to Algorithms by Cormen et al., we see the following pseudo-code for the same partitioning:

This piece of code seems to be identical to the one from Wikipedia. Moreover, seems like the code would fail on their example. Because I understand this very unlikely to be the case for them to make this mistake, I'm wrong somewhere.

So my questions are:

1. What am I getting wrong?
2. Can `hi` be used for pivoting or there is a very specific fundamental reason to pick `A[lo]`?

# Answer
> 8 votes
**"The devil is in the details".** Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.

The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last two lines of code is how to determine the index that will be used by that first two lines of code to split the part of array between `lo` and `hi`.

```
#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#
        if i >= j:
            return j

```

**The above version, as in OP's post and as in Wikipedia, is correct.**

However, as mentioned by OP, the above version with its middle line of code changed to `pivot = A[hi]` will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $\[0,1\]$ or $\[1,0,2\]$.

**When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A\[hi\] instead of A\[lo\]", it means the following variant.** On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to `lo` and `hi`. In fact, since only one splitting index is returned when two indices `i`and `j` crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.

```
#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#
        if i >= j:
            return i

```

The posted code as in problem 7.1 of CLRS's *Introduction To Algorithms*, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $\[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21\]$. I suspect that you missed the part ***e*** of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function `quick_sort_hoare` . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go over that problem closely.

---
Tags: sorting, quicksort
---


title: Solving equations without side effects

text:
# Question
Title: Solving equations without side effects
Consider the example of solving for $x$ where $Ax=b$. This is not in general function, there can be more than one solution. So if you make such a solver in a functional style...does this count as a side effect?

`def solve(A:Matrix[Float],b:Matrix[Float]):Matrix[Float] = ...`

Obviously the solution will be dependent on several internal factors such as the method to solve, e.g. the type of echolonization, or perhaps it uses randomization (Krylov methods for example). And that appears to be all you could expect because solving is not a function. Still, it is evident that the return is a representative of an equivalence class, and so subject to the interpretation that the outputs are representative of an equivalence class then this would be a function -- just we don't want to implement it as some coset of a subspace as that might be slower or impossible.

In purely functional programming is there a loop-hole of sorts for implementing relations -- which interpretted under an equivalence relation, become fucntions, even if we don't explicitly wrap it up that way?

E.g. could I implement a version of the signature above for `solve` in Haskell without a monad?

# Answer
> 3 votes
As far as I know, I think it is possible to build a functional implementation of `solve` that *does* behave as a deterministic function, with no side effects. Yes, there might be multiple possible outputs that are all valid. However, I think it's possible to pick an implementation where it always outputs the same answer. (Certainly, the existence of multiple possible outputs doesn't on its own render it impossible to build such an implementation.)

Here is a simpler example, to give you some intuition. Suppose we want to find a solution to $|x|=c$, where $c$ is a constant given in advance. Then there are two solutions ($x=+c$ and $x=-c$). Nonetheless, you can still build a functional program to output a solution to this, i.e., on input $c$, the code returns a solution to $|x|=c$. An example implementation is the identity function (always return whatever the input was). This is functional and has no side effects.

So just because there are multiple valid outputs doesn't require the code to randomly or nondeterministically choose among them. Often you can write code that outputs one of them, and is consistent and deterministic about which one it outputs.

For instance, here is a plausible such implementation for your particular problem:

1. Solve the linear system "minimize $x\_1$ such that $Ax=b$" using linear programming. (Here I write $x\_1$ for the first variable of $x$, i.e., I am assuming $x=(x\_1,\dots,x\_n)$.) (If it has no solution, return "No solution".) Let $u^{(1)}$ denote the resulting such solution.
2. Solve the linear system "minimize $x\_2$ such that $Ax=b$ and $x\_1 = u^{(1)}\_1$" using linear programming. Let $u^{(2)}$ denote the resulting such solution.
3. Solve the linear system "minimize $x\_3$ such that $Ax=b$ and $x\_1 = u^{(1)}\_1$ and $x\_2 = u^{(2)}\_2$" using linear programming. Let $u^{(3)}$ denote the resulting such solution.
4. Repeat, until you have obtained $u^{(n)}$, where $n$ is the number of variables. Return $u^{(n)}$.

Note that this algorithm returns the lexicographically least solution to $Ax=b$. Because linear programming is in P, I believe each "solve the linear system" step can be implemented with a deterministic, functional algorithm.

---
Tags: functional-programming
---


# Question
Title: Is the problem to construct a $\mathcal{O}\mbox{*}(1.4^n)$ (or better) time algorithm for subset sum still open?
Is the problem to construct a $\mathcal{O}\mbox{\*}(1.4^n)$ (or better) time algorithm for subset sum still open? I wanted to check the problem before finishing a paper.

The most recent reference I found to this open problem is on next paper:

> 'SETH-Based Lower Bounds for Subset Sum and Bicriteria Path, Amir Abboud et al.' 2017 link

citing:

> 'Open problems around exact algorithms, Woeginger' 2008 link.

# Answer
The way to tell if it is open is to read more recent papers to see if any of them make progress. If not, it's still open. The way to find more recent papers is to look up that paper on Google Scholar and look through all the papers that site it. If someone has made progress, it's likely they'll cite that paper.

In general, don't expect to necessarily find a paper somewhere that says "it's still open". People aren't necessarily going to bother repeating "yup, still open" every year.
> 2 votes

---
Tags: algorithms, time-complexity, np-complete
---


# Question
Title: Optimal substructure and dynamic programming for a variant of the rod cutting problem
The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

> Given a rod of length $n$ inches and a table of prices $p\_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r\_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$): $$R(i) = \max\_{1 \le j \le i} \Big(p\_j + R(i-j)\Big),\\; R(0) = 0,$$ where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

> we also have limit $l\_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

***Problem:*** Is this variant of the rod cutting problem solvable using dynamic programming?

# Answer
> 1 votes
***Answer My Own Question:***

Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max\_{1 \le j \le i \land L\_j \ge 1} \Big(p\_j + R\big(i-j, L\[j \mapsto L\_j-1\]\big)\Big),$$ where $L\[j \mapsto L\_j - 1\]$ leaves other length limit than $L\_j$ unchanged.

---
Tags: algorithms, optimization, dynamic-programming, recurrence-relation
---


# Question
Title: What are some problems in $\mathrm{P}$ with time complexity of high-degree polynomial?
What are some problems that are in $\mathrm{P}$ but the best known algorithm has a high-degree polynomial ($\ge 3$) time complexity?

# Answer
**Concrete example**: Thorup's $O(n^{120})$ time algorithm to recognize half-squares of planar bipartite graphs.

https://arxiv.org/abs/1804.05793

**Parameterized problem**: Some parameterized $NP$-complete problems have arbitrarily large polynomial time algorithms. Like, finding a $k$-clique in a graph can be solved by $\Theta(n^k)$ algorithm. And we do not know how to do much better. There might be some improvement but in general when the parameter increases the degree of the polynomial run-time bound increases also.

Computational geometry problems parameterized with the number of dimensions $d$ can be seen as a special case in this group.

Some other $NP$-complete problems (like Vertex Cover in the comment of kne below) have parameterized version with linear-time algorithm for each parameter value. So, it takes some careful investigations before naming a hard parameterized problems.
> 2 votes

# Answer
> What are some problems that are in $\mathrm{P}$ but the best known algorithm has a high-degree polynomial ($\ge 3$) time complexity?

Polynomial time always makes me think of nested loops, such that $\ge \operatorname{O}\left(n^3\right)$ looks like "*nest three-or-more loops*".

So, optimizing $f\left(x\_0 , \\, x\_1 , \\, \dots , \\,x\_m \right) ,$ where:

* $f$ is a black-box function;
* each $x\_i$ has $n$ distinct values; and
* $m \ge 2 .$
> 1 votes

# Answer
For an integer $k$, let $P\_k$ be the following problem: The input is a program $p$ in your favourite programming language. The question is whether $p$ halts after at most $|p|^k$ steps, where $|p|$ is the input size (the length of the program $p$). Unless the chosen programming language is very unusual, every $P\_k$ is decidable in polynomial time; yet for every exponent $e$, there is some $k$ such that $P\_k$ requires $\Omega(n^e)$ time. This is an application of the time hierarchy theorem.

The above is an academic example. It is stronger than what you asked for: Not only the best *known* algorithm has a high exponent; all possible algorithms do. An example for a natural problem with a high-ish best-known exponent is primality. There, as far as I know, the exponent is $6$. (To be precise: This is the best known exponent for algorithm. The actual exponent might be lower. In fact, the first estimate for the same algorithm had an exponent of $12$.)
> 1 votes

---
Tags: time-complexity
---


# Question
Title: $a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$?
A related question: How to prove that a bounded pushdown automaton is regular?

Well I proved that $a\_k$ for each $k$ is the set of all the regular language. Thus $\bigcup\_1 ^{\infty} a\_k = \bigcup\_1 ^{\infty}\\{$ the set of all regular languages} = $\\{$ The set of all regular languages $\\}$.

However before noticing that $a=\bigcup\_1^\infty a\_k$ is taking unions of the same set, I thought that the Context-Free-Languages might be a subset of $\bigcup\_1^\infty a\_k$. *So, I wish for someone to point out the flaw of the next explanation*:

Let $L$ a CFL, and $M$ a pushdown automaton which accepts $L$. Now denoting $L\_k = \\{w\in L : M$'s stack size $\le k$ throughout $w$'s reading process $\\}$ each $L\_k$ is a regular language because $L\_k \in a\_k$. (I think that was the shaky point, but I can't explain why this claim is wrong). So $L = \bigcup\_1^\infty L\_k \in\bigcup\_1^k a\_k =a$.

# Answer
The flaw is in the claim $\bigcup\_{k=1}^\infty L\_k \in\bigcup\_{k=1}^\infty a\_k$. That is not a valid conclusion. It doesn't follow from the fact that $L\_k \in a\_k$ for each $k$.

(Consider: just because $3 \in S\_1$ and $5 \in S\_1$, it doesn't follow that $3+5 \in S\_1 \cup S\_2$. Just because $L\_1 \in S\_1$ and $L\_2 \in S\_2$, it doesn't follow that $L\_1 \cup L\_2 \in S\_1 \cup S\_2$. Just because $L\_k \in a\_k$ for each $k$, it doesn't follow that $\bigcup L\_k \in \bigcup a\_k$. In fact, it is correct that $L\_k \in \bigcup a\_k$ holds for each $k$, but $\bigcup L\_k \in \bigcup a\_k$ doesn't hold; the regular languages are not closed under infinite unions.)

You won't always have us to check every dubious proof, so let me teach you two techniques you can use if you run across a proof that you are suspicious/skeptical of:

1. If you're not sure whether to be convinced of a proof, try taking each individual step and writing out a detailed proof of it. If you started with a 4-line proof sketch, this might turn into a 40-line proof, so it's tedious, but it's often a good way to discover whether the proof is valid (sometimes when it comes time to write down the justification, you discover that that step that looks obvious in writing isn't actually so obvious).
2. Pick a specific example and work through what the logic of the proof is saying about that example. Check whether the logic is valid for that particular example.

For instance, pick $L= \\{0^n 1^n : n \in \mathbb{N}\\}$; this is perhaps the canonical CFL that isn't regular. Work through what your proof claims about that $L$, and check each statement to see if it is valid. Well, $L\_k = \\{0^n 1^n : n \le k\\}$, and sure enough, it is correct that $L\_k \in a\_k$ for each $k$. It is also correct that $L = \cup\_{k=1}^\infty L\_k$. However, when you check the claim that $\bigcup\_{k=1}^\infty L\_k \in\bigcup\_{k=1}^k a\_k$, you discover that the claim is not correct, as the left-hand side is $L$ and the right-hand side is the set of all regular languages and $L$ is not regular. So, that's the step you should be suspicious of.
> 2 votes

---
Tags: automata, context-free, pushdown-automata
---


title: Is mathematics context-free?

text:
# Question
Title: Is mathematics context-free?
Anyone who deals with mathematics knows intuitively that it is a different kind of thinking than ordinary common-sense thinking that intelligent people use every day to understand and make decisions in the world.

I would like to understand what separates ordinary common-sense thinking from mathematical thinking, and I have a guess that ordinary common-sense thinking is in essence contextual, while mathematics in in essence non-contextual.

For instance, pure mathematicians do not care about the context of a mathematical equation, how the equation relates to the real world, when trying to solve the equation, but ordinary intelligent people almost always care about the context of statements made in daily life.

So I thought that perhaps the Chomsky hierarchy might help me answer this question. This gives a mathematical definition of languages which are context-sensitive and context-free. So my question is "Can the structure of mathematics, as represented by ZFC (or perhaps the Peano axioms), be represented as a context-free language."

Has any work been done on this?

# Answer
Let me quote the question.

> Can the structure of mathematics, as represented by ZFC (or perhaps the Peano axioms), be represented as a context-free language?

I would like to clarify that the phrase "the structure of mathematics" could be understood as mathematical structures or as a philosophical term whose definition is up in the air in everybody's mind. While everybody is entitled to define or understand that phrase in their own terms, I object to the view "the structure of mathematics, as represented by ZFC (or perhaps the Peano axioms)" because of its ambiguity and its likely misleading connotations. **Mathematics is larger than what can be represented by ZFC**. Even assuming the view that mathematics is all about ZFC, the clearer way to express that view is "all statements in mathematics, as generated by ZFC (or perhaps the Peano axioms)".

Let me also emphasize that the questions "what is mathematics?" and "what is mathematical thinking?" have been asked thousands of times if not billions of times since the birth of mathematics. Numerous articles, books, videos etc have been produced about them. Checking whether it is context-free sounds like a new cool line of thinking to me on first look, though.

Here is an equivalent of version of the question.

> Is the set of all statements generated by ZFC (or by the Peano axioms) a context-free language?

Here is my answer. **No, the statements generated by ZFC or the Peano axioms is not a context-free language. It is, in fact, undecidable.** Please note that any context-free language is decidable.

In fact, **any consistent formal system within which a certain amount of elementary arithmetic can be carried out is undecidable**. Note that the subject of previous sentence should, if one wants to know the exact meaning of "a certain amount", be understood according to *"Gödel's Incompleteness Theorems"* by Panu Raatikainen, 2015, *Stanford Encyclopedia of Philosophy*. The Peano axioms is just one of the many formal systems where enough elementary arithmetic can be carried out. The most upvoted answer to why Peano arithmetic is undecidable shows that the undecidability of Peano arithmetic (and, in fact, that of any consistent formal within which a certain amount of elementary arithmetic can be carried out) follows from the way the proof of Gödel's incompleteness theorem goes. I would encourage you to read that well-written answer.

---

Please note there is a serious ambiguity or inconsistency in the original question and the equivalent version given above. By common understanding of a context-free language, it has a finite set of terminal symbols and a finite set of production rules. Since there are infinitely many natural numbers in Peano axioms, which are considered as terminal symbols, we have infinitely many terminal symbols in the statements generated by Peano axioms. There are a few approaches to resolve this technicality so that we could obtain a non-vacuous question as intended by OP. For example, we can replace Peano axioms by a set of axioms where each positive number is defined as the successor of the number that is one smaller than it (then we need infinitely many axioms). For another approach, we can introduce a bit of set theory and define $1$ as the set $\\{0\\}$, $2$ as the set $\\{0, 1\\}$, $3$ as the set $\\{0, 1, 2\\}$, and so on (then it might not be called Peano axioms by common views, I believe). For still another approach, we can extend context-free language to include language with (countably) infinite many terminals. In whichever reasonably way we resolve this technicality, the answer should remain negative following the same line of arguments.
> 3 votes

---
Tags: formal-languages, chomsky-hierarchy
---


# Question
Title: Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?
We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$.
I came up with following *proof* but i dont know it's correct or not.
$$g = O(f)$$ $$g \le c\_1\*f $$ $$h \le c\_2\*f $$

Now we have to prove, $$g = O(h)$$ $$g \le c\_3\*h$$ $$g \le c\_3\*c\_2\*f $$ $$ c1 \le c3\*c2 $$ We can find $c\_3$ such that last equation $ c1 \le c3\*c2 $ will be true.

> Is this correct or not? If not what will be correct proof for this?

# Answer
> 1 votes
$f(n)=n^2$, $g(n)=n$, $h(n)=1$.

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


title: Proving Monotonicity of Softmax Layer

text:
# Question
Title: Proving Monotonicity of Softmax Layer
In the book here: http://neuralnetworksanddeeplearning.com/chap3.html

If you scroll down to Exercise 2 in the Softmax Section, it says

> Show that $\partial a^L\_{j}/\partial z^L\_{k}$ is positive if $j=k$ and negative if $j \neq k$. As a consequence, increasing $z^L\_j$ is guaranteed to increase the corresponding output activation, $a^L\_j$, and will decrease all the other output activations.

Here, $$a\_j = \frac{e^{z^L\_{j}}}{\sum\_{k}{e^{z^L\_{k}}}}$$

I managed to prove the part when $j \neq k$ by differentiating as normal to get $$-\frac{e^{z^L\_{j}}}{\left(\sum\_{k}{e^{z^L\_{k}}}\right)^2}$$

which is obviously always negative. However I'm having trouble with when $j=k$. When I differentiated I got an inequality which simplified to proving $$\sum\_{k}{e^{z^L\_k}}\>1$$ I am unsure of how to do this.

# Answer
Let's remove the $L$ superscripts. The derivative with respect to $z\_L$ is $$ \frac{\partial a\_j}{\partial z\_j} = \frac{e^{z\_j} \sum\_k e^{z\_k} - e^{z\_j} e^{z\_j}}{\left(\sum\_k e^{z\_k}\right)^2} = \frac{e^{z\_j} \sum\_{k \neq j} e^{z\_k}}{\left(\sum\_k e^{z\_k}\right)^2} \> 0. $$
> 2 votes

---
Tags: artificial-intelligence, neural-networks
---


title: Principle of Duality

text:
# Question
Title: Principle of Duality
I would like to know how to alter/add NOTs when applying Duality principle.

Suppose I have P = XY(X+Y) + NOT(Y), how to find its dual?

My book says that while applying Duality Principle to a relation:

* Change all 0s to 1s
* Change all ORs to ANDs
* Change all ANDs to ORs

But it doesn't say anything about NOTs.

# Answer
> 3 votes
In the dual boolean algebra, NOT is the same NOT operation we have in the original boolean algebra.

Your book does not say anything to handle NOT because there's nothing that needs to be done. Simply leave the NOTs unaffected in your formula.

# Answer
> 3 votes
Let's start with the definition:

> The dual of a Boolean function $f(x\_1,\ldots,x\_n)$ is the function $f' = \lnot f(\lnot x\_1,\ldots,\lnot x\_n)$.

Here $\lnot$ is negation. The idea of the definition is to switch True and False, both for the input variables and for the output.

Suppose now that the function $f$ is given over the "de Morgan basis". This is the smallest collection $F$ of functions such that:

* $0,1 \in F$.
* $x\_i \in F$ for every variable $x\_i$.
* If $g \in F$ then $\lnot g \in F$.
* If $g,h \in F$ then $g \lor h, g \land h \in F$.

Here $\lor$ is OR and $\land$ is AND.

We can now give a recursive procedure for dualizing a function:

* If $f = 0$ then $f' = \lnot 0 = 1$.
* If $f = 1$ then $f' = \lnot 1 = 0$.
* If $f = x\_i$ then $f' = \lnot \lnot x\_i = x\_i$.
* If $f = \lnot g$ then $f' = \lnot \lnot g = \lnot g'$.
* If $f = g \lor h$ then $f' = \lnot (g \lor h) = \lnot g \land \lnot h = g' \land h'$.
* If $f = g \land h$ then $f' = \lnot (g \land h) = \lnot g \lor \lnot h = g' \lor h'$.

---
Tags: boolean-algebra
---


title: Intuition for maxterms

text:
# Question
Title: Intuition for maxterms
I understand that in terms of minterms,

F (Boolean Function) = Sum of Products and thus will yield true when either of the products is true.

But I am unable to develop any intuition for maxterms,

F(Boolean Function) = Product of Sums (of maxterms).

Is F = Product of sums just a different way of representing F = Sum of Products?

If yes, is it possible to prove that using the duality principle?

# Answer
> 3 votes
Indeed, maxterm is the concept dual to minterm. As you mention, $$ f(x) = \bigvee\_{y\colon f(y)=1} \text{"$x=y$"} = \bigvee\_{y\colon f(y)=1} \bigwedge\_{i=1}^n \text{"$x\_i=y\_i$"}. $$ Here $\vee$ is OR (your addition), $\wedge$ is ADD (your multiplication), the input is $x = x\_1,\ldots,x\_n$, and "$x\_i=y\_i$" is either $x\_i$ (if $y\_i$ is True) or $\bar{x}\_i$ (if $y\_i$ is False).

Similarly, we have $$ f(x) = \bigwedge\_{y\colon f(y)=0} \text{"$x \neq y$"} = \bigwedge\_{y\colon f(y)=0} \bigvee\_{i=1}^n \text{"$x\_i \neq y\_i$"}. $$ This time "$x\_i\neq y\_i$" is $x\_i$ if $y\_i$ is False, and $\bar{x}\_i$ if $y\_i$ is True.

---

When the function is monotone, we can improve on the first representation: $$ f(x) = \bigvee\_{\text{$y$ minterm}} \text{"$x \geq y$"} = \bigvee\_{\text{$y$ minterm}} \bigwedge\_{i\colon y\_i=1} x\_i. $$ Here "$x \geq y$" means $x\_i \geq y\_i$ for all $i$, and a minterm is a satisfying assignment of $f$ which is minimal in the sense that changing any 1 to 0 changes it to an unsatisfying assignment.

We can define maxterms analogously – maximal unsatisfying assignments, and then $$ f(x) = \bigwedge\_{\text{$y$ maxterm}} \text{"not $x \leq y$"} = \bigwedge\_{\text{$y$ maxterm}} \bigvee\_{i\colon y\_i=0} x\_i. $$

---
Tags: boolean-algebra
---


title: Finding a strong loop invariant

text:
# Question
Title: Finding a strong loop invariant
Pseudocode:

```
if n < 2
    return false
while n != 1
    if n % 2 != 0
        return false
    n = n/2
return true

```

The loop will terminate when n is odd. If n = 1, true is returned and that means that n0 was a power of 2. Otherwise it's false.

I'm new at this and struggle with the proving the power of 2 part for before and during iterations and after the loop terminates. Also what does a loop invariant look like for a true vs false return on a loop?

Is it reasonable to say something like:

at the every iteration i, 1 \<= n \<= n0/(2^i)
true returned when n = 1 and n0 is a power of 2
false returned when n is odd and n \> 1

Is it possible to even make strong loop invariant here without referencing the initial value of n?

# Answer
> 2 votes
One loop invariant is "$n\_0/n$ is a power of 2 and $n \geq 1$", where $n\_0$ is the original value of $n$.

The loop invariant holds initially (before the first iteration of the loop) since $n\_0 = n$, and $n\_0 \geq 2$. As for what happens in the loop, there are several cases:

* If $n$ is odd then $n = 2k+1$ for some $k$; since $n \> 1$ (otherwise the loop would have terminated), moreover $n \geq 3$, and so $n\_0 = 2^t (2k+1)$ for some $t \geq 0$ and $k \geq 1$, showing that $n\_0$ isn't a power of 2.
* If $n$ is even then the value of $n$ in the next iteration is $n' = n/2 \geq 1$, and so $n\_0/n' = 2n\_0/n$ is also a power of 2.

If the loop terminates naturally then necessarily $n = 1$, and so the loop invariant guarantees that $n\_0 = n\_0/n$ is a power of 2.

Finally, since $n/2 \< n$, the value of $n$ keeps decreasing; since always $n \geq 1$, it cannot decrease forever, i.e., the loop terminates. In fact, the running time is $\Theta(\log n)$.

---
Tags: loop-invariants
---


# Question
Title: How to determine whether a dependent type that doesn't fit the monad instance is categorically a monad
<sup>\[Using Idris syntax and terminology, but the question is not about Idris\]</sup>

If a monad interface (or type class) has a constraint requiring applicative functor, a monad instance can be written by implementing either bind: `(>>=) : Monad m => m a -> (a -> m b) -> m b`, or `join : Monad m => m (m a) -> m a`, or both. However, this is a much more constrained and specific type of monad than the general concept of monad in category theory.

In a dependently typed language, it is not uncommon to stick some kind of size into the type in order to allow the typechecker to recognize well-founded recursion, etc. The unfortunate impact is that because bind and join may not be size-preserving operations, you can loose your monad instance, and thus not be able to use whatever syntactic sugar the language may provide, etc. That's okay though; let's set that aside. What I'm wondering more fundamentally is if you've only lost your instance of `Monad`, or if your type has actually stopped being a monad. If you have a type `k : Nat -> Type -> Type`, might not `pure : a -> k n a` and `(>>=) : k n a -> (a -> k m b) -> k (op n m) b` / `join : k n (k m a) -> k (op n m) a` still satisfy the conditions to be a monad for some `op : Nat -> Nat -> Nat`, e.g. `+`?

I'll give a specific example: a freer monad indexed by size in order to allow for total operations.

```
||| http://okmij.org/ftp/Computation/free-monad.html
module Freer

%default total
%access public export

data FFree : (Type -> Type) -> Nat -> Type -> Type where
  FPure   : a -> FFree g n a
  FImpure : g x -> (x -> FFree g n a) -> FFree g (S n) a

Functor (FFree g n) where
  map f (FPure x)     = FPure (f x)
  map f (FImpure u q) = FImpure u (map f . q)

pure : a -> FFree g n a
pure = FPure

promote : {m : Nat} -> FFree g n a -> FFree g (n + m) a
promote (FPure x)     = FPure x
promote (FImpure u q) = FImpure u (promote . q)

assocS : (m : Nat) -> (n : Nat) -> m + S n = S (m + n)
assocS Z n = Refl
assocS (S m) n = cong $ assocS m n

apply : FFree g n (a -> b) -> FFree g m a -> FFree g (m + n) b
apply {n} {m} (FPure f) x =
  promote $ map f x
apply {n=S n} {m} (FImpure u q) x =
  let y = flip apply x . q
  in rewrite assocS m n in FImpure u y

bind : (a -> FFree g n b) -> FFree g m a -> FFree g (n + m) b
bind {n} {m} f (FPure x) = promote $ f x
bind {n} {m=S m} f (FImpure u f') =
  let y = bind f . f'
  in rewrite assocS n m in FImpure u y

join : FFree g m (FFree g n a) -> FFree g (n + m) a
join = bind id

```

This allow my monad methods to be total for my freer monad. But... is it still a valid monad? I do not see why adding some typelevel information would stop it from being one; other than some typelevel fanciness in the form of `rewrite ... in ...` etc. the method implementations are the same as those given in the "Freer Monads, More Extensible Effects" paper. However, I am used to seeing the monad laws written in terms of `Monad`, which I am no longer able to implement here since e.g. `Free g 3``Free g 2`.

How do I prove or disprove that, `Monad` interface and syntactic sugar aside, I still have a monad here?

# Answer
> 4 votes
So, there are potentially many answers to this sort of question. One is that there are many possible categories on which there can be monads. The rules for establishing that something is a monad will ultimately be the same, but the details will differ depending on the specific category chosen. So, since there is a natural number index involved, perhaps a monad on a category of natural number indexed types is in order, although your presentation is not precisely that. Or, perhaps you can also quantify over the natural number to get a monad that is the 'total space' of all the individual fibers. (It's also not clear to me why you need the index in this example, unless Idris has a feature that makes the type small because of it.)

However, another answer is that whether something 'is a monad' is kind of the wrong thing to worry about. Especially with examples like this, what is going on is that we are constructing the 'free algebra' of some embedded language we want to work with. Monads show up because they are one of the ways that algebra is dealt with in category theory. So *because* we're doing algebra, we can phrase it in terms of (a particular construction of certain) monads. But it can also be presented it in other ways as well.

The presentation you're using originates in Haskell (I think), and it's convenient there, because of impredicativity and no concern for logical consistency/termination. You can easily write down the, 'free monad over a type operator.' It's also convenient because Haskell has features that make things presented as `Monad` nicer to use than other presentations.

However, if Idris is not (as) accepting of definitions like that, it seems sensible to re-evaluate whether some other presentation that *is* accepted can encode all the things you want. For instance, there are ways of specifying strictly positive functors in more obvious ways, which give rise to e.g. W-types:

```
data W (A : Type) (B : A → Type) : Type where
  con : (a : A) → (y : B a → W A B) → W A B

```

and it's possible to construct free monads based on this:

```
data Free (A : Type) (B : A → Type) (X : Type) : Type where
  pure : X → Free A B X
  branch : (a : A) → (B a → Free A B X) → Free A B X

```

This is the free monad over the polynomial functor given by `A` and `B` (the `A`-fold sum of `B a`-fold products of `X`). But this is by no means the only option.

So, it seems to me that *unless* there is some syntax sugar or similar reason to prefer a particular solution (or you have other reasons), it's better to worry about whether you have built the algebraic structure you wanted in a way that is easy to use for whatever you actually wanted to use it for, and not whether it adheres to some particular way of doing it that works well in a different language.

And to loop around, if the size is just there for getting everything to termination check, maybe it also doesn't matter if it's any actual notion of monad from category theory. If you erased the sizes and it fit the definition of a normal monad, and the sizes are only there for book keeping, maybe that's good enough (as long as it doesn't obstruct you in more practical ways).

---
Tags: dependent-types, category-theory
---


# Question
Title: is the alignment between two sequences of points with 'no cross line' constraint an NP problem?
Given two sequences of points(i.e. ordered points), connect the points in seq\_A with the points in seq\_B according to some rules. A point could be connected to 0, 1, or many points in the other sequence. But there should not be any line crossing. And each line could be assigned with a weight(controlled by relation between two connected points) and the overall weights should be as low as possible.

Is this an NP problem? Can this problem be reduced to any of Karp's 21 NP-complete problems?

Thanks to David Richerby. The constraints that were missing are that the number of points that are not connected to any points should also be as few as possible.

# Answer
You could prove that something is in **NP** by reducing it to an **NP**-complete problem. However, it's usually much easier to just demonstrate a nondeterministic polynomial-time algorithm that finds a solution, and even easier to demonstrate a deterministic polynomial-time algorithm that verifies a given solution.

Now, the trivial answer to your question is "No, this is not in **NP**" because there's a type error. **NP** is a class of decision problems (i.e., problems where the answer is "yes" or "no"), whereas your problem is to compute some object that minimizes some criterion. However, the decision version of your problem is in **NP**: this is the problem where you're given a target weight $w$ and asked if there's a solution with weight at most $w$. It's easy to check deterministically in polynomial time that a proposed solution does have weight at most $w$.

Beyond that, there's not much to say. Your problem seems under-specified to me because the trivial solution "Don't match anything at all" has weight zero, which is best possible as long as the weights are non-negative. If you tighten up the definition of the problem, my guess is that the non-crossing requirement constrains the problem so much that it will have a deterministic polynomial-time solution. For example, if you match the first element of sequence $A$ to anything other than the first element of sequence $B$, then the first element of sequence $B$ can't be matched to anything without crossing. This suggests that dynamic programming will give an efficient solution.
> 0 votes

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