title: Two transition functions def of NP

text:
# Question
Title: Two transition functions def of NP
I've seen a definition of NP alluded to in different texts where at each step an NDTM makes a nondeterministic choice between two transition functions and behaves accordingly. It seems like even in a binary alphabet the machine has more than two possible behaviors.

Can anyone formalize this and help me understand why this is equivalent to more common definitions? Or if anyone had a reference maybe. Thank you.

# Answer
You can choose from among four options by first making one binary choice, then making a second binary choice; there are $2\times 2=4$ total possible outcomes, each of which can be mapped to one of those four options. Similarly, you can choose among any finite set using only binary choices. That's why the two are equivalent.
> 1 votes

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


title: Is the ABC-partition problem NP-hard?

text:
# Question
Title: Is the ABC-partition problem NP-hard?
In the **ABC-partition problem**, there are three sets $A, B, C$ with $m$ positive integers in each. The sum of all integers is $m T$. The goal is to construct $m$ triplets with the same sum $T$, each of which contains exactly one integer from $A, B$ and $C$.

The problem "feels" NP-hard, but I could not find a proof for this. I could only find reductions in the wrong direction:

But, none of these reductions shows that ABC-partition is NP hard.

Previously I asked specifically about a reduction from 3-partition from ABC-partition; now I am not even sure if it is NP-hard. Is it?

# Answer
> 1 votes
I did not find the proof claimed by Garey and Johnson at \[SP16\]. But I found two other proofs, which seem independent (do not rely on the existing proof):

# Answer
> 2 votes
This seems to be the Numerical 3D matching problem. Wikipedia cites a proof of NP-Hardness by Garey and Johnson (problem SP16).

---
Tags: reductions, partitions
---


# Question
Title: Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?
$L=\\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\\}$

I tried writing $L$ as the union of the language created with $j$ odd and the one with $j$ even.

When $j$ is odd, I can prove using the pumping lemma that it is not a cfl.

When $j$ is even, I can prove that it is a cfl by writing a context-free grammar for it.

But then the union of a cfl and a non-cfl doesn't really help me prove $L$ is a cfl or not.

How do I proceed?

# Answer
> 1 votes
We can prove $L$ is not a CFL using the pumping lemma by choosing the string $a^pb^{1}a^{p^2+1}$, where $p$ is the constant in the pumping lemma.

Since $|vwx|\le{p}$, we can have:

If $v$ or $x$ contains more than one type of letter, so when we pump the order breaks.

If both $v$ and $x$ contain only $a$'s then when we pump the sum breaks because we either don't add enough letters or we add too much(the case with $i^2$ when pumping the first $a$'s).

The only other case is when either $v=b$ or $x=b$ that we solve by pumping $v$ down to 0, so the new string will match the $j$ even case with $j=0$, but $i + j = p^2$ while $k = p^2 + 1$.

# Answer
> 1 votes
Note that the context-free languages are closed under left-quotient as well as intersection with regular languages, as John L. noted.

Assume, for contradiction, that $L$ was context-free. Then $$L\_1 := L \cap a^\*ba^\* = \\{a^iba^{i^2 + 1} : i \geq 0\\}$$ and $$L\_2 := a^\*ba \setminus L\_1 = \\{a^{i^2} : i \geq 0\\}$$ must be context-free as well. If $L\_2$ is context-free then it must also be regular, since it only contains one letter.

But using the Pumping lemma for regular languages it can be shown that $L\_2$ isn't regular, contradicting our assumption that $L$ is context-free ↯

---
Tags: formal-languages, context-free, pumping-lemma
---


title: Lambda Calculus vs Turing Machine

text:
# Question
Title: Lambda Calculus vs Turing Machine
How functional programming using lambda calculus is analogous to construction of Turing machine as per computational aspects?

# Answer
> 2 votes
The short answer is that every computation describable in lambda calculus can be computed on a turing machine, at the same time every Turing machine program can be converted into a lambda calculus.

The long answer would include proofs that both of those statements are true but that's a bit out of scope for this site.

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


# Question
Title: Can a Code Script be Optimized for Time and Space Complexity Using Logic Gates
let's say that I have a Python script that performs various operations, including data manipulation, conditional logic, and iteration. However, I'm concerned about its time and space complexity efficiency. Would it be possible to use logic gates to optimize code by simplifying and reducing redundant logic using techniques like Karnaugh Maps (K-Maps) or transforming the script into a logic gate representation and then optimizing it?

I'm curious if it's feasible to take a complex Python script translate all the raw machine code operations it does and simplify it using logic gates to achieve the most efficient time and space complexity possible. Are there any specific strategies or tools that can help in this process? How would one transform a Python script into a logic gate representation, and what steps are involved in optimizing it? Additionally, are there any limitations or trade-offs to consider when using this approach? Any insights or examples would be greatly appreciated!

# Answer
How much money do you have?

There is at the moment no technology that could create configurable hardware that is faster than a general purpose CPU. (Improving configurable hardware would improve the general purpose CpU as well).

Apple has improved existing CPUs, I'd say that cost them maybe ten billion dollars. That’s why I asked “how much money do you have”.

If you want Python to run faster, translate it manually into C or C++, or build a compiler that is specialised. If you don’t need the generality of Python most of the time, just-in-time compilers can do very well. But if you want to build hardware, that will cost you. Probably the first step wouldn’t be asking on stackexchange but finding the first 20 million dollars and hire 100 people to work on finding a solution full time.
> 0 votes

# Answer
Python is an imperative language, meaning any operation can have side effects. This makes such "gate level" thinking tricky. Its written in a way such that there's no issue with a block of memory being the name of a person at one point and becoming a control flow variable in the next.

This means any attempt to convert it into the raw gates has to be done with a sense of time ordering to it. You can't just start by converting into gates by digging down into how the machine code works beacuse you would need to solve too large of a problem. If you have 100 billion transistors on a chip, you need to model a system to reproduce an arbitrary interweaving of 100 billion transistors per CPU cycle, easily leading into the large numbers we typically don't use in English, like septililon.

Its tricky to reduce this because Python and the machine language code were designed from a particular reduction already: the reuse of those 100 billion transistors in a well controlled manner governed by a CPU clock. You would be hard pressed to come up with a more efficient mapping than the one they were designed for.

You might have better luck with functional languages, like Haskell. They provide a structure for side effects from day 1 (they forbid them, forcing you to cleverly specify all side effects as return values).

But in the end, if you want to get down to gates, the correct way to do so is to use a language designed for that in the first place, such as VHDL.

That's not to say there's not optimizations to be had. We have many optimization tools available. But they optimize to their strong point: they optimize to operation on a CPU, rather than a generic lattice of gates.
> 0 votes

---
Tags: time-complexity, reductions, runtime-analysis, logic, space-complexity
---


# Question
Title: Data structure to keep track of cache hit ratio?
In a web application, I use a map as a simple in-memory cache/lookup.

* A key is a string, say `A` and maps to an integer value, say `50`.
* The app handles thousands of requests per minute. Requests need to look up keys.
* If the key isn't found in the map, then the value is computed and stored under they key as `map[A]=50`
* Next time a request comes in for the key `A`, the cache returns `map[A]`, which is `50`.

I'd like to keep track of the hit ratio of cache lookups. If the hit ratio is close to $0$, then the cache doesn't work, almost no items are found. If the hit ratio is close to $1$, we're happy, most lookups of keys are cached and avoid expensive computation.

I tried several approaches, with mixed results:

(1) Once the app starts, we initialize two counters `hit=0` and `total=0` and just count up: `total` always, `hit` if a key was found. If the app runs with high cache hit ratio for a long time (say, days) it takes very long to reflect a prolonged 100% cache miss rate.

(2) Initialize the counters as above, but every $t$ minutes, we

* calculate there the ratio `hit/total` and log it.
* reset `hit` and `total` to $0$ again.

This kind of works, but if the amount of cache lookups is irregular in the time frame (for example for a few minutes no lookup at all) then for that interval the rate can be $0$ or if there's one successful lookup then the hit rate will be $1$. Also results can be skewed, see (3).

(3) Keep a ring buffer with $n$ entries, each entry is a cache lookup that's either $1$ or $0$. It's a sample of the latest $n$ lookups and doesn't depend on time. But the sample can be skewed, say we have $1000$ entries in the ring buffer and the same key is requested $1000$ times and is never found (for example due to a software bug), then if another $1000$ lookups happen for a different key and they succeed, they overwrite all the previous data, skewing the result.

---

These are techniques I could come up with - but are there any standardized approaches for this? Some data structures or sampling algorithms that could accommodate for skewness but still provide a valid approximation of the true underlying lookup rate?

I'm not very well versed in this field and would be glad for any pointers/additional literature I should review.

# Answer
What you're looking for is not so much a data structure as a problem statement. What is it that you're trying to learn from a metric such as a hit-count? The structures need to match what you're doing with the data.

From the sound of it, the data you wish to work with is a time history of hit ratios. You want to be able to look at a window and say "these time ranges went bad. Go look at what was happening then."

A common solution is to start from (2) and manipulate the data. Capture all activity within some *short* time period, and then log the result. Then manipulate the data to show you what you want to see. For example:

* Keep a FIFO of these log datas (rather than individual hits), and output the hit ratio for the entire FIFO buffer (a longer period).
* Keep a weighted average of the last score and the most recent score. This works like a FIFO except it weights the more recent entries heavier, and only requires O(1) space, rather than the O(n) where N is the length of the FIFO.
* Output more than one number, or create a combined metric. Maybe you need to output *both* hit-ratio and total hits to identify when the total count was too low for the hit-ratio to be meaningful. Or maybe you scale the hit-count towards 1 when the ratio is low because you intend to ignore those times.
* Determine what you really want to know about your cache and apply statistics. If you actually know what you want to learn from the metric, you may be able to apply Bayesian analysis to *correctly* weight the data where total-count is low.
* If you're worried about high-volume times where you need to respond quickly, you might even be able to skip the hit/total counters and do the Bayesian analysis on the individual cache hits and cache misses.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Finding optimal sequence of attacks to minimize number of soldiers needed
## The problem

Trying to improve my algorithms I bumped into a problem by Pedro Pablo Gómez Martín and Marco Antonio Gómez Martín, which I can summarise like this:

> You are given a list of enemy bases you want to conquer. You can only attack one base at a time. Each base $i$ requires a minimum number of soldiers $s\_i$ to be conquered, will take out a certain number $b\_i$ of the soldiers who attack and will require a certain number $r\_i$ of soldiers to stay back holding it, as you move the remaining army to the next battle.
>
> The following relationship will always hold for a base $i$: $s\_i \geq b\_i$. Note that it is possible that $r\_i \gt s\_i$.
>
> Determine the best sequence to follow in order to minimize the number of soldiers needed to conquer all bases.

I know, given a certain order, how to compute the number of soldiers needed, and the solution space is finite, so brute-forcing it is always a possibility, but far from ideal. It looks like there is a greedy algorithm to find the right order.

## My work

### Finding the minimum number of soldiers needed for a given order

I found a series of inequations which I believe give me the number of soldiers $x$ needed to conquer and hold $n$ bases if attacked in from $1$ to $n$:

* We need enough soldiers to conquer the first base: $x\_{a} = s\_1$
* Before each subsequent battle, we need enough soldiers to take it after all the losses of the previous battles: $x\_{b} = \max\limits\_{2 \leq i \leq n} ( s\_i+\sum\limits\_{j=1}^{i-1}(b\_j+r\_j))$
* We want enough people to survive to be able to keep the last base: $x\_{c} = \sum\limits\_{i=1}^{n}(b\_i+r\_i)$

So I believe the minimum number of soldiers needed $x$ to hold and retain all is $x = max(x\_{a}, x\_{b}, x\_c)$. I think these equations can be used to prove that a certain order is optimal or not, though how exactly escapes me.

### Finding the right order to minimise the number of soldiers needed

The key insights I figured out are:

* The army gets weaker with each battle, so the battles which require more people should be fought first, when the army is at its strongest (decreasing order of $s\_i$).
* The losses matter more the sooner they happen. Hence, we should first fight the battles which will immobilise the least number of soldiers (increasing order of $b\_i + r\_i$).

Neither criterion by itself is enough to find the optimal solution in all cases.

## My question

The proper solution seems to be combining the previous two insights into a single metric: decreasing order of $si - (b\_i + r\_i)$. Attacking the bases in that order seems to guarantee a minimum number of soldiers needed, or at least that's what my tests indicate.

While I get an intuititon of how that way "combines" both insights, I can't figure out why it *guarantees* the optimal order. Why that metric and not, for example, decreasing order of $\frac{s\_i}{b\_i+r\_i}$? Or some weighted combination?

I'd appreciate some help both proving mathematically that it is optimal (using my equations or some other way), and ideally gaining some intuition.

# Answer
> 3 votes
Okay! In order to (hopefully) prove that your proposed greedy algorithm is correct, we will make an argument that is very common when dealing with greedy algorithms (as you can see from @D.W. 's linked question).

So, suppose you have found an $x$ such that there exists at least one sequence of battles where the army will survive. That is, there is some sequence of battles $\mathcal{B} = (s\_1,b\_1,r\_1),\ldots,(s\_n,b\_n,r\_n)$, such that we have $x \geq \sum\_{j=1}^{i-1} (b\_j+r\_j)+s\_i$ for all $i$ and also $x \geq \sum\_{i=1}^n (b\_i+r\_i)$. Then we also have the sequence of battles given by your greedy algorithm: $\mathcal{B'} = (s\_1',b\_1',r\_1'),\ldots,(s\_n',b\_n',r\_n')$. And we want to show that if the army survives sequence $\mathcal{B}$, then they also survive sequence $\mathcal{B'}$.

To do so, we look at the *smallest* index $k$ where $(s\_k,b\_k,r\_k) \neq (s'\_k,b'\_k,r'\_k)$. Since these are just two different orderings of the same battles, there is some $t\>k$ such that $(s\_t,b\_t,r\_t) = (s'\_k,b'\_k,r'\_k)$. Now, the idea is to change the ordering such that $(s\_t,b\_t,r\_t)$ comes between $(s\_{k-1},b\_{k-1},r\_{k-1})$ and $(s\_k,b\_k,r\_k)$.

Now, what happens if the army does not survive this modified sequence? That means that there is some other index $i$ such that $x-(s\_i+(b\_t+r\_t)) \< \sum\_{j=1}^{i-1} (b\_j+r\_j)$. It should quickly be clear that $k\leq i\<t$ (therefore we did not overcount the battle at index $t$ in the previous formula). But what does this imply for the original sequence, where the battle at index $t$ came at index $t$?

Since $(s\_t,b\_t,r\_t)$ was equal to $(s\_k',b\_k',r\_k')$ in the greedily generated sequence, and the two sequences were equal for all indices lower than $k$, we can infer that $(s\_i,b\_i,r\_i) = (s\_{i'}',b\_{i'}',r\_{i'}')$ for some $i'\>k$. From the way the battles were sorted in $\mathcal{B'}$, we therefore know that $s\_t-(b\_t+r\_t) \geq s\_i-(b\_i+r\_i)$. Reordering gives $s\_t+(b\_i+r\_i) \geq s\_i+(b\_t+r\_t)$. Putting it all together, we get this inequality: $x-(s\_t+(b\_i+r\_i)) \leq x-(s\_i+(b\_t+r\_t)) \< \sum\_{j=1}^{i-1} (b\_j+r\_j) \leq \sum\_{j=1}^{t-1} (b\_j+r\_j)-(b\_i+r\_i)$.

This means that the army would not survive the original sequence of battles, $\mathcal{B}$! This calculation was derived from the assumption that the army did not survive the modified sequence; therefore that assumption must be wrong.

Now we know that as long as the chosen sequence differs from the greedy sequence at least at one point, we can just move the greedy choice to that point and still get a sequence where the army survives. Therefore the greedy sequence itself must always be among those where the army survives. Note that the trick with looking at the first index where the two sequences differ is a standard trick when proving greedy algorithms correct, and it is well worth it to familiarize oneself with this technique.

# Answer
> 2 votes
@Highheath has given an excellent and concise answer already.

I came up (with the help of some friends) with a much longer one, which I still think it's worth posting. Maybe it's because I worked on it for a few hours, but I find it easier to comprehend despite its length.

---

It is important to distinguish the purpose of $s\_i$, $b\_i$ and $r\_i$. $s\_i$ represents the number of people needed to *win* battle $i$. You may win a battle but not be able to hold the base: if you have $m$ soldiers march into battle $i$, after the battle you have $m-b\_i$ soldiers alive, and if $m-b\_i \lt r\_i$, you will not be able to hold the base. So $s\_i$ simply represents the number of people needed to *win* the battle, not not necessarily to hold the base afterwards.

For simplicity, let's call $l\_i=b\_i+r\_i$ to the loss of people in battle $i$, i.e. the number of soldiers which are not available for further battles after battle $i$, because they were casualties or had to stay behind holding the base.

## Corollary 1

> For $n=2$, sorting in descending order of $s\_i - l\_i$ results in the minimum number of soldiers needed.

Let's take two bases, called $B\_a$ and $B\_b$.

$B\_a$ requires $s\_a$ soldiers to be taken, and will incur in a loss of $l\_a$. Similarly, $B$ requires $s\_b$ soldiers, and will incur in a loss of $l\_b$ soldiers.

Let's state that $s\_a - l\_a \geq s\_b - l\_b$. This means that $s\_a + l\_b \geq s\_b + l\_a$ (1).

#### Case 1: We attack $B\_a$ before $B\_b$.

In order to guarantee winning all battles and holding all bases, we need:

* Enough soldiers to win the first battle: $s\_a$
* Enough soldiers to win the second battle after the first one: $s\_b+l\_a$
* Enough soldiers to withhold all casualties and soldiers left behind: $l\_a+l\_b$ $$x\_1 = \max(s\_a, s\_b+l\_a, l\_a+l\_b)$$

#### Case 2: We attack $B\_b$ before $B\_a$.

In order to guarantee winning all battles and holding all bases, we need:

* Enough soldiers to win the first battle: $s\_b$
* Enough soldiers to win the second battle after the first one: $s\_a+l\_b$
* Enough soldiers to withhold all casualties and soldiers left behind: $l\_a+l\_b$ $$x\_2 = \max(s\_b, s\_a+l\_b, l\_a+l\_b)$$

Let's consider all three values that $x\_1$ might take, and realise that in all cases, $x\_2 \geq x\_1$. We can do this by seeing that, for any value $x\_1$ takes, there is at least one value in the three possible values which $x\_2$ may take which is greater or equal than $x\_1$, so $x\_2 \geq x\_1$:

* If $x\_1 = s\_a$, $x\_2$ will be at least $s\_a+l\_b$
* If $x\_1 = s\_b + l\_a$, we know that one of the values of $x\_2$, $s\_a+l\_b$, is greater than $x\_1$ (see (1))
* If $x\_1 = l\_a + l\_b$, $x\_2$ will be at least $l\_a + l\_b$

So it is proven that, given two bases, is optimal to attack them in decreasing order of $s\_i - l\_i$.

---

## Lemma 1

> The optimal relative order of $B\_a$ and $B\_b$ ($B\_a$ attacked before $B\_b$) remains the same if a third base $B\_c$ is inserted between the two, provided that $s\_a - l\_a \geq s\_c - l\_c \geq s\_b - l\_b$

We can prove this by comparing the two alternatives:

#### Case 1: $B\_a \rightarrow B\_c \rightarrow B\_b$

We need enough soldiers to:

* Take the first base: $s\_a$
* Take the second base after the first battle: $s\_c + l\_a$
* Take the third base after the first two battles: $s\_b + l\_a + l\_c$
* Survive all losses: $l\_a + l\_b + l\_c$

$x\_{1}=\max(s\_a, s\_c+l\_a, s\_b+l\_a+l\_c, l\_a+l\_b+l\_c)$

#### Case 2: $B\_b \rightarrow B\_c \rightarrow B\_a$

We need enough soldiers to:

* Take the first base: $s\_b$
* Take the second base after the first battle: $s\_c + l\_b$
* Take the third base after the first two battles: $s\_a + l\_b + l\_c$
* Survive all losses: $l\_a + l\_b + l\_c$

$x\_{2}=\max(s\_b, s\_c+l\_b, s\_a+l\_b+l\_c, l\_a+l\_b+l\_c)$

We can prove that $x\_{1} \leq x\_{2}$ using the same method as for *Corollary 1*: for any possible value of $x\_{1}$, the value of $x\_{2}$ will be greater or equal than that.

* If $x\_{1}=s\_a$, $x\_{2}$ will be at least $x\_{2}=s\_a+l\_b+l\_c$
* If $x\_{1}=s\_c+l\_a$, $x\_{2}$ will be at least $x\_{2}=s\_a+l\_b+l\_c$. This is because $s\_a - l\_a \geq s\_c - l\_c$, so $s\_a + l\_c \geq s\_c + l\_a$, and therefore, $s\_a + l\_b + l\_c \geq s\_c + l\_a$
* If $x\_{1}=s\_b + l\_a + l\_c$, $x\_{2}$ will be at least $x\_{2}=s\_a+l\_b+l\_c$. This is because $s\_a-l\_a \geq s\_b-l\_b$, so $s\_a+l\_b \geq s\_b+l\_a$. By adding $l\_c$ to both sides of the inequation, $s\_a+l\_b+l\_c \geq s\_b+l\_a+l\_c$
* If $x\_{1}=l\_a + l\_b + l\_c$, $x\_{2}$ will be at least $x\_{2}=l\_a+l\_b+l\_c$.

So, as long as $s\_a - l\_a \geq s\_c - l\_c \geq s\_b - l\_b$ holds, $B\_a$ must be attacked before $B\_b$.

---

## Lemma 2

> Given a sequence of battles, we can replace them with a single equivalent battle

We can prove this by induction, starting with $n=2$. Given two battles $B\_j$ $(s\_j, b\_j, r\_j)$ and $B\_k$ $(s\_k, b\_k, r\_k)$, we can say the following:

* In order to win both battles, we need enough soldiers to win the first one *and* to win the second one after the first one: $s\_{jk}=\max(s\_j, s\_k+l\_j)$.
* After fighting both battles, $b\_{jk}=b\_j + b\_k$ soldiers will have been taken out.
* After fighting both battles, $r\_{jk}=r\_j + r\_k$ soldiers will be posted to keep the bases.

Note that $s\_{jk}$ does not include the requirement of having enough people to hold all bases, because $s$ only represents the number of people needed to win a battle.

So we can replace the sequence with an equivalent battle $B\_{jk}$ $(\max(s\_j, s\_k+l\_j), b\_j + b\_k, r\_j + r\_k)$

For any value of $n \ge 2$, we can simply iteratively reduce the first two battles into one until only one base is left.

---

## Lemma 3

> For a sequence $B\_1 \rightarrow B\_2 \rightarrow ... B\_{n-1} \rightarrow B\_{n}$ sorted in decreasing order of $s\_i-l\_i$, if the middle sequence of $n-2$ bases is replaced with their single equivalent base $B\_2'$, the resulting $B\_1 \rightarrow B\_2' \rightarrow B\_{n}$ sequence is also in decreasing order of $s\_i-l\_i$

First we'll prove this for $n=4$. Let's start the demonstration with four bases sorted in decreasing order of $s\_i-l\_i$, $B\_1 \rightarrow B\_2 \rightarrow B\_3 \rightarrow B\_4$.

We know that the following inequalities are true: $s\_1 - l\_1 \geq s\_2 - l\_2 \geq s\_3 - l\_3 \geq s\_4 - l\_4$

We replace $B\_2 \rightarrow B\_3$ with $B\_{23}$, with $s\_{23}=\max(s\_2, s\_3+l\_2)$ and $l\_{23}=l\_2+l\_3$ (*Lemma 2*):

$B\_1 \rightarrow B\_{23} \rightarrow B\_4$

We want to prove that the following relationship holds: $s\_1 - l\_1 \geq s\_{23} - l\_2 - l\_3 \geq s\_4 - l\_4$

For this we, once again, examine the possible values of $s\_{23}$:

#### Case 1: $s\_{23}=s\_2$

We want to prove: $s\_1 - l\_1 \geq s\_2 - l\_2 - l\_3 \geq s\_4 - l\_4$, which has two parts:

Since $s\_1 - l\_1 \geq s\_{2} - l\_2$, trivially $s\_1 - l\_1 \geq s\_{2} - l\_2 - l\_3$.

On the other hand, if $s\_{23}=s\_2$, we know that $s\_2 \geq s\_3 + l\_2$ (or $s\_{23}$ would have taken a different value). By adding the two known inequalities $s\_3 - l\_3 \geq s\_4 - l\_4$ and $s\_2 \geq s\_3 + l\_2$, we reach $s\_3 - l\_3 + s\_2 \geq s\_4 - l\_4 + s\_3 + l\_2$. Simplifying and reordering, we reach $s\_2 - l\_2 - l\_3 \geq s\_4 - l\_4$.

#### Case 2: $s\_{23}=s\_3+l\_2$

We want to prove: $s\_1 - l\_1 \geq s\_3 - l\_3 \geq s\_4 - l\_4$, which we already know to be true.

This ends the proof for *Lemma 3* for $n=4$. This is trivially generalisable to $n\>4$: first, replace $B\_2$ and $B\_3$ with their single equivalent base $B\_{23}$, and that should leave the sequence still in order. Then replace $B\_{23}$ and $B\_4$ with $B\_{234}$, etc.

---

## Conclusion

We have proven that, if we sort our list of bases according to the $s\_i - l\_i$ (i.e. $s\_i - (b\_i+r\_i)$) criterion, for any two distinct bases $B\_i$ and $B\_j$ that we choose, their relative order will be optimal:

* If they are consecutive, the optimality is proven by *Corollary 1*.
* If they are not consecutive, the bases in the middle can be reduced to a single equivalent base (*Lemma 2*), and the resulting sequence will still be sorted according to our criterion (*Lemma 3*). In that case, the optimality is proven by *Lemma 1*.

Since all bases are optimally sorted with respect to all other bases, the sorting of the whole list is optimal.

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


title: Mapping Reduction from HALT?

text:
# Question
Title: Mapping Reduction from HALT?
I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would finish my proof that L isn't even recognizable. Now I'm stuck. I just can't seem to master creating mapping reductions.

I know I need to develop f() where: if (〈M〉,w) is in HALT, then f(〈M〉,w) = 〈M'〉 is in co-L and if (〈M〉,w) is **not** in HALT, then 〈M'〉 is **not** in co-L but I've wasted a day and a half on this on reduction.

I'd really appreciate some guidance on a general strategy for developing the function, f(). I keep getting caught up in w versus c and the input (which I called x) to M'.

Thank you for any direction.

# Answer
> 0 votes
Define the reduction $f$ such that $f(\langle M, w \rangle) = \langle M' \rangle$, where $M'$ is a TM that on word $x$

1. simulates $M$ on $w$ if $x = c$
2. halts

It's easy to see that

$$M \text{ halts on } w \iff M' \text{ halts on } c$$

therefore

$$\langle M, w\rangle \in \texttt{HALT} \iff f(\langle M, w \rangle) = \langle M'\rangle \in \overline{L}.$$

So $\texttt{HALT} \preceq\_{M} \overline{L}$.

---
Tags: turing-machines, computability, reductions, halting-problem, decidability
---


# Question
Title: Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language
I've been working on proving that this language

```
L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)}

```

is not Context Free. "na(x)" stands for "number of a's in the string x".

I however can't find a string where all possible divisions of the string can be pumped out of the language. For example, I tried a^(p+1) b^(2p+1), but I can pick the last a and the first two b's and pump them however I like, without the string exiting the language.

I attached an image with the full text of the exercise and why I think that the provided solution is wrong.

What am I missing here? Also, if the language actually is free, what would be the context free grammar for it?

# Answer
The language *is* context-free. Slightly different: Context free grammar construction $\\{ a^mb^n \mid m≤n≤2m \\}$.

For strings where the symbols $a,b$ may be in any order, you might find inspiration in the language $\\{w∈\\{a,b\\}^∗:\\#\_a(w)=2\\#\_b(w)\\}$.
> 3 votes

# Answer
Suppose that instead of a stack, you had a single counter, $x$, that you could either increment or decrement, under the control of a non-deterministic finite-state machine. (Each transition of the finite-state machine either increments $x$, decrements $x$, or leaves it unchanged.)

Can you think of how to recognize the language with such a machine?

Hint:

> When you see a `b`, decrement $x$. When you see an `a`, non-deterministically either \____ or \_____. You fill in the blanks.

Can you think about how to convert such a machine into a pushdown automaton? (It is known that they can be converted -- these machines are called one-counter machines, which are known to be equivalent to pushdown automata.)

Hint:

> Somehow encode the value of $x$ on the stack. What are reasonable options for how you might represent an integer?

You might take a look at Context free grammar construction for inspiration and ideas.

You'll have to fill in the details, as it is your exercise.
> 2 votes

# Answer
As the other answers indicate, the language is indeed context-free.

Writing a grammar for it is a bit tricky, but we can do it as follows.

---

## $N\_a(x) = N\_b(x)$

First, let's consider the (much) simpler language where every string has the *same* number of *a*'s as *b*'s.

We don't need a very methodical approach to find that it can be written as this grammar (using *Q* (for "equal") as its start symbol, rather than the traditional *S*, to avoid confusion when I discuss other languages below):

$Q \rightarrow \epsilon$
$Q \rightarrow QQ$
$Q \rightarrow aQb$
$Q \rightarrow bQa$

. . . but it may help to think through why this works.

Taking our cue from D.W.'s answer, we can imagine iterating over the string while keeping a counter, adding 1 to the counter every time we see an *a* and subtracting 1 from the counter every time we see a *b*. At the end, the counter shows $N\_a(x) - N\_b(x)$, which is 0 if and only if there are the same number of *a*'s as *b*'s, that is, if and only if the string is in the language.

The reason that the above grammar covers all possibilities is that there only are four "paths" the counter can take from 0 back to 0:

1. It might never leave 0. This happens only if the string is empty.
2. It might cross 0 at one or more points along the way. In this case, the string can be split at the first point, giving two non-empty substrings that are also members of the language.
3. It might remain above 0 the whole way. In this case, the string must start with *a* (bringing the counter to 1) and end with *b* (bringing it down from 1 to 0), and the substring in between must also have the same number of *a*'s as *b*'s (because the counter ends up at the same value where it started, namely 1).
4. It might remain below 0 the whole way — this case is symmetric to #3.

(Note that the production rules "overlap" in a way that these cases don't — it would be valid to apply $Q \rightarrow QQ$ and $Q \rightarrow \epsilon$ a whole bunch of times for no reason — but these cases demonstrate why each production rule is necessary, and why they're collectively sufficient, to cover all valid strings. Also note that I'm not demonstrating that these production rules *only* generate valid strings; I think that's clear enough without further explanation.)

---

## $N\_a(x) \le N\_b(x) \le 2N\_a(x)$

OK, so, let's kick it up a notch, and consider a language that's a bit closer to yours. Here, every string has at least as many *b*'s as *a*'s, and at most twice as many *b*'s as *a*'s. (That's still simpler than your language, which uses strict inequalities instead of weak ones, but obviously it's more complex than the first language.)

We can apply similar reasoning as above, except that now, each *a* is allowed to balance out either 1 or 2 *b*'s; so when we iterate over the string with a counter, we can add *either* 1 *or* 2 when we see an *a*, and a string is in the language if there's *any way* that this could result in the counter ending up back at 0. (This is what D.W. mentioned in his/her first hint.)

That puts a bit of a wrench in our case analysis, because it's now possible to cross 0 by "jumping" from −1 to +1, which means that the counter might register 0 at the end of a string of the form *b…b* even if it never registered 0 at any point in the middle. More generally, it's now possible to "jump" from *x* to *x*+2. (But the reverse is not true: the counter can't jump downwards from *x* to *x*−2.)

But, we can still take the same approach, just taking that into account. So, these are the cases:

1. The value of the counter might never leave 0. This happens only if the string is empty.
2. It might take the value 0 at one or more points along the way. In this case, the string can be split at the first point, giving two non-empty substrings that are also members of the language.
3. It might never take the value 0, but jump from −1 to +1 at some point along the way. In this case, the string must start with a *b* that lowers the counter from 0 to −1, then later have an *a* that raises the counter from −1 to +1, and end with a *b* that lowers the counter from +1 to 0.
4. It might remain above 0 the whole way. In this case it must start with an *a*, and can't end with *a* or *ab* unless the whole string is *ab*.
5. It might remain below 0 the whole way. In this case it must end with an *a*, and can't start with *a* or *ba* unless the whole string is *ba*.

which gives this grammar (using *W*, for "weak inequality", as the start symbol):

$W \rightarrow \epsilon$
$W \rightarrow WW$
$W \rightarrow bWaWb$
$W \rightarrow ab$
$W \rightarrow aWbb$
$W \rightarrow ba$
$W \rightarrow bbWa$

(Note: the rules $W \rightarrow ab$ and $W \rightarrow ba$ could also be written as $W \rightarrow aWb$ and $W \rightarrow bWa$ without changing the resulting language, but I figured it was clearer to hew a bit closer to the case analysis.)

---

## $N\_a(x) \lt N\_b(x) \lt 2N\_a(x)$

OK, finally, the language we're actually interested in.

Observe that we must have $N\_a(x) \ge 2$, otherwise there's no valid value for $N\_b(x)$. So $N\_a(x) \ge 2$ and $N\_b(x) \ge 3$, and the condition $N\_a(x) \< N\_b(x) \< 2N\_a(x)$ can be written as $N\_a(x) - 2 \le N\_b(x) - 3 \le 2(N\_a(x) - 2)$. This means that an element of this language can be thought of as an element of the prior language plus 2 extra *a*'s and 3 extra *b*'s. (Please take a moment to convince yourself of this.)

What's more, with the exception of *bbaaabb*, any string in this language must have a substring of length 5 that contains exactly 2 *a*'s and 3 *b*'s. This is because:

* As we've seen, it must have length at least 5, which means it must have at least one substring of length 5.
* If it has a length-5 substring with fewer than 2 *a*'s and a length-5 substring with more than 2 *a*'s, then it must have a length-5 substring with exactly 2 *a*'s, because consecutive same-length substrings overlap in all but one character, so their number of *a*'s can differ by at most one. (For example, *aaaaabbbbb* contains the substring *aabbb* on its way from *aaaaa* to *bbbbb*.)
* If all of its substrings have fewer than 2 *a*'s, then it has least 4 *b*'s between any two *a*'s, which means it has at least two *b*'s per *a*, which is not allowed.
* If all of its substrings have more than 2 *a*'s, then . . . this case is a bit trickier. Let's write its length as 5*m* \+ *k*, where *k* is in {0,1,2,3,4}. The first 5*m* characters contain at least 3*m* *a*'s and at most 2*m* *b*'s, so they leave a deficit of at least *m* \+ 1 *b*'s; so the last *k* characters need at least *m* \+ 1 more *b*'s than *a*'s. Since *m* is at least 1, and the last *k* characters can have at most 2 *b*'s, the only solution is *m* = 1, *k* = 2 (for a total of 7 characters), with both of those last two characters being *b*'s. Applying the same logic from the right end of the string, we find that the first two characters must also be *b*'s, and the overall string must be *bbaaabb*.

This means that (1) any string from this language can be formed by inserting either *bbaaabb* or a permutation of *aaabb* somewhere in a string from the prior language (*W*), and (2) conversely, a string formed by doing that will be a string from this language.

Let's label those eleven possible insertions (*bbaaabb* and the ten permutations of *aaabb*) with the nonterminal *I*:

$I \rightarrow bbaaaabb$
$I \rightarrow aabbb$
$I \rightarrow ababb$
$I \rightarrow abbab$
$I \rightarrow abbba$
$I \rightarrow baabb$
$I \rightarrow babab$
$I \rightarrow babba$
$I \rightarrow bbaab$
$I \rightarrow bbaba$
$I \rightarrow bbbaa$

And our production rules for this language's start symbol *S* are just copies of those for *W* (which we carry forward), except that they also ensure that an *I* gets inserted in there somewhere:

$S \rightarrow I$
$S \rightarrow WSW$
$S \rightarrow bSaWb$
$S \rightarrow bWaSb$
$S \rightarrow aSb$
$S \rightarrow aSbb$
$S \rightarrow aWbSb$
$S \rightarrow bSa$
$S \rightarrow bbSa$
$S \rightarrow bSbWa$

(Actually, some of those might be redundant — I'm not sure if $S \rightarrow aWbSb$, for example, enables any strings that would otherwise be impossible — but that's OK, redundant production rules don't make the grammar invalid!)
> 2 votes

---
Tags: formal-languages, context-free, pumping-lemma
---


title: Insert a node in a binary search tree

text:
# Question
Title: Insert a node in a binary search tree
The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $z.p = y$ instruction does. wouldn't the algorithm work without it?

```
abr_insert(T, z) //z is the node that must be inserted
    {
            y = NULL;
            x = T.root;
            while(x != NULL)
            {
                    y  = x;
                    if(z.key < x.key)
                            x = x.left;
                    else
                            x = x.right;
            }
            z.p = y; //here is the instruction that I don't understand
            if(y = NULL)
                T.root = z;
            else if(z.key < y,key)
                    y.left = z;
            else
                    y.right = z;
    }

```

# Answer
It seems like this algorithm is keeping track of parent pointers. Each node `N` has three fields: `N.left` (left child), `N.right` (right child), and `N.p` (parent). The variable `y` is used to keep track of the most recent parent, so when we fall off the tree (i.e. when `x == NULL`) we can use `y` as the parent of the new node `z`.
> 4 votes

# Answer
Yes, this particular method doesn't use the y.parent pointer. However, other methods rely on it. Consider finding `successor`:

1. Traverse to the right if x.right is present to find smallest key greater than x.key
2. If the right subtree of node x is empty and x has a successor y, then y is the lowest `ancestor` of x whose left child is also an ancestor of x

Python code:

```
def successor(self, x: Node):
    if x.right:
        return self.min(x.right) # traverse the right subtree to get a min
    y = x.parent
    while y and x == y.parent: # go "down" the tree using y.parent
        x = y
        y = y.parent
    return y

```
> 0 votes

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


# Question
Title: Examples of algorithms best their class that require cyclical data structures
I remember that the Roc Lang website claimed that their choice to forbid any form of cyclic data structures prohibited their customer to implement some of the best in their class algorithms, id est some algorithms that are better than everything else solving the problem that they are designed to solve.

I have tried in some trivial manners to find some algorithm which as described by Roc lang is the best in their class but cannot be implemented in Roc Lang given the choice to forbid any kind of cyclic data structures which includes double linked lists, graphs with cycles, arbitrary acyclic directed graph and more; have been unable to find any example of such algorithms.

Can please you give examples of some algorithms?

# Answer
Any graph algorithm that works on general graphs (i.e., is not restricted to acyclic graphs) qualifies. You should be able to look through your favorite textbook and find many algorithms that work on graphs.

For instance, you could consider shortest-path algorithms.
> -1 votes

---
Tags: algorithms, graphs, data-structures
---


# Question
Title: DFA that accepts strings ending with an even number of 1 in the last three characters ("000","110","101","011")
I need to design a binary DFA to accept strings where the last three characters read are either "000", "110", "101" or "011".
My brutal solution is:

---

I need help either reducing this one or with a simpler solution. Thanks

# Answer
> 2 votes
There are some merging of states that you could make, but the minimal automaton is still quite big, I think:

* states with the same number of characters are not equivalent, because either one is final and not the other, or you could read one or two more letters to get into a final state for one and not the other.
* the state $S$ cannot be equivalent to another state, because it is the only one at distance $3$ of any final state;
* for a similar reason, the states $0$ and $1$ cannot be equivalent to any other;
* a 2-characters state $ab$ can only be equivalent to a 3-characters $cde$ if $ab = de$ and $cde$ is not final. One can note that since the following pairs are non-final states with the same exiting transitions, they are equivalent:
    + $00$ is equivalent to $100$;
    + $01$ is equivalent to $001$;
    + $10$ is equivalent to $010$;
    + $11$ is equivalent to $111$.

You'd get a $11$ states automaton.

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


# Question
Title: Prove that balanced binary search tree has lowest expected cost
Take numbers from 1 to 100. Put all of them in a binary search tree. Now, one of those 100 numbers is picked uniformly at random and given to us. We'd like to find it in the binary search tree. The tree should be constructed in a way that the expected number of comparisons in minimal. It's intuitive that a balanced tree where we always go to the middle element and select it as the next child will be optimal. In other words, go to the median, 50 and make it the root. Then go to the median of the left elements, 25 and make it the left child and the median of the right elements, 75 and make it the right child and so on.

But I'm unable to prove this in general. For the case of 100, one could simply create the binary tree with this strategy and verify that every level has the largest possible elements. But how to do it for general n?

# Answer
Firstly, note the following claim:

**Claim**: Let $S$ be any set of $n$ elements. Let $B$ be any binary tree with $n$ empty nodes. Then, there exists a mapping of $S$ to the nodes of $B$ such that $B$ is a binary search tree of set $S$.

**Proof**: The claim follows since inorder traversal of the tree can be mapped to sorted set of elements in $S$.

Next, note that searching an element in a binary search tree (BST) has cost equal to the *level* of that element in the tree. Therefore, the expected cost of searching an element in the tree is $\sum\_{i \in S} \ell(i)/n$, where $\ell(i)$ is the level of element $i$ in the tree.

Let $B$ be a balanced binary search tree over $S$, with maximum level $L$ (assume the root node has level $1$). Let $B'$ be any unbalanced binary search tree with level $\geq L+1$. Let $N\_o$ be any node at level $\geq L+1$. The node can be moved to a lower level since there exists an empty location with level $\leq L$. The level of node $N\_o$ decreases by at least $1$. Repeat this process till all the nodes at level $\geq L+1$ are moved to levels $\leq L$. This is feasible since there exists a tree $B$ where all nodes can fit in levels $\leq L$. For each node moved, the level of node decreases. However, the tree will no longer be a *search tree*. However, the above claim states that there exists a mapping of nodes to the elements in $S$ that makes the tree "binary search tree". Thus, the expected cost of the new tree, which is balanced, is smaller than the unbalanced tree.

---

**Why the tree constructed by "choosing median recursively" gives the minimum expected cost?**

**Proof**: Let $k$ be such that $n = 2^{k}-1+m$, where $m \< 2^{k}$. Then, after the first iteration, each subtree has at least $\lfloor (2^{k}-1+m-1)/2 \rfloor$ nodes $\geq 2^{k-1} - 1 + m'$, where $m' \< 2^{k-1}$. Inductively, after $k-1$ iterations, the number of nodes in any subtree is at least $1$. Thus, all the levels from $1$ to $k-1$ are completely filled. These nodes constitute a total of $2^{k}-1$ nodes. Therefore, the nodes at the last level are $m$. The last level is $k$, which is $= \lceil \log n \rceil$. This is the minimum possible level for a binary tree. Moreover, since all the nodes at lower levels are filled completely, $m$ is the minimum number of nodes that appear at the last level. This also implies that $\sum\_{i \in S} \ell(i)$ is minimum; thus the expected cost of searching in the tree is minimum.
> 2 votes

# Answer
The cost for searching a node in a BST is the node's depth in the BST.

What you need to show is that the average depth is lower in a balanced BST than in any BST.

An informal way to see it is that if the BST is not balanced, then you could delete one of its leaf to put it in a lower depth.

Note that if the set of value of your BST is $S$, then for any binary tree structure of size $|S|$, there is exactly one BST that can be labeled with $S$. What that means is that to prove your result, you only have to work on tree structure, and not on labelling.
> 3 votes

---
Tags: optimization, binary-trees, binary-search-trees
---


# Question
Title: Using naturality to prove $f: \forall\alpha. \alpha\times\alpha\to\alpha$ must be a projection
Suppose we have a System F term $f : \forall \alpha. \alpha\times\alpha\to\alpha$, interpreted in a parametric model which is a bicartesian closed category.

I was wondering if in such context it is possible to prove that (in the model) $f$ must be a projection (either $\pi\_1$ or $\pi\_2$), exploiting the naturality of $f$ and little else.

So far, I got the following sketch.

By naturality, for all $g: A\to B$, we have $$ (g \times g); f\_B = f\_A ; g$$ In particular, we can take $A = 2 = 1+1$ (the coproduct of the final object with itself), and take ${\sf tt},{\sf ff}: 1\to 2$ to be the inclusions.

We get that, for all $g: 1\to B$, we have $$ \langle {\sf tt}, {\sf ff} \rangle ; (g \times g); f\_B = \langle {\sf tt}, {\sf ff} \rangle ; f\_2 ; g$$ Now, we have a morphism $$ h = \langle {\sf tt}, {\sf ff} \rangle ; f\_2 : 1 \to 2 $$ and we assume that (\*) in the model $h$ must be one of $\sf tt,ff$ -- i.e., that no other morphisms exist.

W.l.o.g., assume $h=\sf tt$ (the other case being symmetrical). Then, we have $$ \langle {\sf tt};g , {\sf ff};g \rangle ; f\_B = {\sf tt} ; g$$ and, taking $g = \[m,n\]$ for some $m,n : 1\to B$ $$ \langle m , n \rangle ; f\_B = m$$ which is "close" to stating that $f\_B$ is the first projection.

Questions:

1) Can we weaken the assumption ($\*$) in some way? Or, can we strengthen ($\*$) by requiring some standard property that "usually" holds in known models? I mean, I could work in a specific model (e.g. PERs) where we only have two inclusions $1\to 2$, but maybe there's some more general standard-ish assumption which can guarantee that?

2) Can we prove that $f\_B$ is really a projection? Proving that it is such seems to require a sort of extensionality principle like

$$ (\forall x:1\to A. x;f=x;g) \implies f=g $$

but this, I guess, might not hold in general.

A final note: I'm aware that one can prove $f$ to be $\beta\eta$ equivalent to a projection through syntactic means (Krivine does so, if I remember correctly), but I am really interested in the consequences of naturality.

# Answer
Naturality is sufficient.

An easy way is to use the Yoneda lemma, which gives the equivalence:

$$ a\times a\to a \equiv (\mathbb2 \to a ) \to a \equiv \mathbb2 $$ where $\mathbb2$ denotes the Boolean type and it is assumed that the arrow $a\times a\to a$ is a natural transformation.

We can adapt the proof of the Yoneda lemma to this case and find a simple proof from naturality:

Suppose $$p : \forall a.\\,a \times a \to a$$ is a function implemented somehow in System F, and suppose $p$ obeys its naturality law. (That assumption will follow from parametricity, but that's not the question here.) Set the type parameter as $a = \mathbb2$ and apply $p$ to the specially chosen value $x : \mathbb 2 \times \mathbb 2$, namely, $x = (true, false)$. The value $p(x)$ is again of type $\mathbb2$ and so we must have $p(x)=y$ where the Boolean value $y$ is either $y=false$ or $y=true$.

Now, use the naturality law of $p$: For any types $a$, $b$, any values $m:a$, $n:a$, and any function $f: a\to b$ we must have: $$ p(f(m), f(n)) = f(p(m, n))$$ Choose $a=\mathbb2$, $m=true$, $n=false$, but keep the type $b$ arbitrary. Then the naturality law says: $$ p(f(true), f(false)) = f(p(true, false)) = f(y) $$

This naturality law constrains $p$ enough to force $p = \pi\_1$ or $p = \pi\_2$. This is because $f(true)$ and $f(false)$ are arbitrary values of type $b$. Denote them by $b\_1 = f(true)$ and $b\_2 = f(false)$. We know that $y$ is either true or false. Suppose $y=false$. Then we have found that for arbitrary values $b\_1$, $b\_2$ of type $b$: $$ p(b\_1, b\_2) = f(false)=b\_2$$ Similarly, if $y=true$ then for arbitrary values $b\_1$, $b\_2$ of type $b$: $$ p(b\_1, b\_2) = f(true)=b\_1$$

We have shown that either $p = \pi\_1$ or $p = \pi\_2$.
> 0 votes

---
Tags: programming-languages, lambda-calculus, category-theory
---


# Question
Title: Resolution on weakening rule by derived clause
How to prove that every clause that is implied by the input formula (learned or not) can be derived using resolution with weakening rule:

$\frac{C} {C \vee D}$

(A clause $C$ is implied by $F$ if for all possible assignments $A$ it holds that $F\[A\]\implies C\[A\]$.)

# Answer
What proof of the completeness of resolution do you know? Chances are it can be easily adapted to this more general setting.

Alternatively, you can reduce it to plain completeness. One way is as follows. Assume a clause $C=l\_1\lor\dots\lor l\_k$ is implied by a CNF $F$. Then the CNF $F\land\let\ob\overline\ob{l\_1}\land\dots\land\ob{l\_k}$ is unsatisfiable, hence it has a resolution refutation. The only way one of the new axioms $\ob{l\_i}$ can be used in the refutation is in a resolution step $$\dfrac{D\lor l\_i\qquad\ob{l\_i}}D.$$ So if you just omit these steps along with the $\ob{l\_i}$ axioms, and perform the remaining inferences as before, you will end up with a valid resolution derivation from $F$ that differs from the original one only in that some extra literals from $C$ are included in some of the clauses. In particular, the derivation ends with a subclause of $C$, from which you can infer $C$ by weakening.
> 2 votes

---
Tags: satisfiability, correctness-proof, first-order-logic, propositional-logic, 3-sat
---


# Question
Title: Algorithm that finds points that are closest to the middle of rectangles in grid
Suppose I have an array of 2D coordinates {x:number,y:number}\[\]. What would be an algorithm that could get me the points that, were an X by Y grid of rectangles laid over the cartesian graph created by the array, are closest to the middle of each rectangle that contains points?

Here's a very **roughly drawn** example:

* 22 (x,y) points
* The top, right, bottom, and left bounds of the imaginary grid are based on the topmost, rightmost, bottommost, and leftmost points.
* This particular grid is broken up into 16 rectangles. The width of all rectangles is the same and the height of all rectangles is the same (though the width might not equal the height)

In this case, the algorithm would return the coordinates of the 13 dots below (again roughly drawn. Some dots were close!).

---

Related question on stackoverflow

# Answer
> 2 votes
The naive approach is the following two steps:

1. For each point, insert it into its respective box in $O(n)$.
2. For each box, iterate every point in it to keep track of the minimum distance to the center and return the point in $O(n)$.

There is no faster algorithm as reading the inputs already takes $O(n)$.

---
Tags: algorithms
---


# Question
Title: Is $L=\{a^nb^m : n\neq 7m, \ n,m\in \mathbb{N}\}$ context free?
I'm asked to categorize the language $L=${$a^nb^m : n\neq 7m, \ n,m\in \mathbb{N}$}, therefor I need to distinguish if it's regular, context free, or non context free (in $P$)

We know CFLs are closed under union, and I belive $L\_1=${$a^nb^m : n\<7m$} can be represented by the CFG $S\rightarrow Ab | aAb | aaAb | ... |aaaaaaAb \\\ A\rightarrow Ab | aAb | aaAb | ... |aaaaaaAb | \epsilon $

(I'm not completely sure in the correctness of this CFG, but I belive it shows the idea of $L\_1$)

However I am unsure on how to represent $L\_2=${$a^nb^m : n\>7m$} in CFG form, it seems like the construction rules of $L\_2$ would be 8 appearences of $a$ per $b$, but theres no upper limit on the number of appearences of $a$, which got me in a freeze in progressing with this.

this prevents me from claiming that $L\_1\cup L\_2=L$ is CFL under closure properties

A little edit: I've created this PA:

which I believe accepts $L\_2$, the basic logic behind it is : read all $a$'s, for each $b$ you see take out 7 appearances of $a$, if you have any $a$'s left in your stack, you can accept the word.

Again, I'm unsure in the correctness of this PA, yet I cant come up with a word in $L\_2$ that wont be accepted by this PA.

# Answer
An easy way prove the language context free is to use the closure properties of context-free languages.

Note that the following grammar with start variable $S$ generates $L' = \\{a^nb^m : n = 7m\\}$

$$S \to a^7Sb | \varepsilon.$$

Therefore

$$L\_1 = a^+L' = \\{a^nb^m : n \> 7m\\}$$

and

$$L\_2 = a^+ \setminus L' = \\{a^nb^m : n \< 7m\\}$$ must be context-free, since the context-free languages are closed under concatenation $\circ$ and (left) quotient $\setminus$ with regular languages. Thus $L = L\_1 \cup L\_2$ must be context-free as well.

---

One way to prove that $L$ is non-regular is to show that the language has an infinite number of unique quotients. We have

$$a^k \setminus L = \\{a^{n - k}b^m : n \geq k \text{ and } n \neq 7m\\}.$$

But since for all $k\_1 \neq k\_2$ follows that $b^{k\_1} \notin a^{7k\_1} \setminus L$ and $b^{k\_1} \in a^{7k\_2} \setminus L$, it follows that for arbitrary $k\_1, k\_2$

$$a^{7k\_1} \setminus L = a^{7k\_2} \setminus L \iff k\_1 = k\_2.$$

So $L$ must have an infinite number of quotients and can't be regular.
> 2 votes

# Answer
You add either 0 to 6 a's on the left and one or more b's on the right, or you add one or more a's on the left. Then you add 7 a's on the left and one b on the right zero or more times.
> 0 votes

---
Tags: context-free
---


# Question
Title: Is this intersection set problem NP-Hard?
Suppose we have collection of n sets $S\_1, S\_2, \dots, S\_n$. Each set has a size of at least $k$. We know for sure that $\exists k$ sets where all of them contain the same $k$ elements; $|S\_1 \cap S\_2 \cap,\dots,\cap S\_k| \geq k$. We don't know the sets nor the intersection elements. I would like to know if these questions are NP-hard or if there is a polynomial algorithm to solve them.

1. Can we find the $k$ intersection elements in $|S\_1 \cap S\_2 \cap,\dots,\cap S\_k| \geq k$?
2. Assume we have set $S\_t$, we would like to know if set $S\_t$ is one of the $k$ sets that have $k$ common elements among them. $S\_t \in ?$ $(S\_1,S\_2,\dots, S\_k)$. In other words, does $S\_t$ intersect with any $k-1$ sets on the same $k$ elements?

# Answer
This is at least as hard as the problem of detecting a $k$-clique in a graph, given a promise that there contains at least one $k$-clique in the graph. In particular, given a graph $G$, let $S\_i$ be equal to the set of vertices adjacent to vertex $i$, along with $i$.

This problem is NP-hard. If you had a polynomial-time algorithm for your problem, then we could use it to solve the clique problem by running it multiple times, once for each possible value of $k$, and checking which is the largest value of $k$ for which it returns a valid $k$-clique.

See also https://en.wikipedia.org/wiki/Clique\_problem and https://en.wikipedia.org/wiki/Planted\_clique.
> 0 votes

---
Tags: complexity-theory, np-complete, np-hard, sets, polynomial-time
---


# Question
Title: Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?
According to Wikipedia, the Church-Turing thesis "states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing machine."

If we made a complete simulation of the human brain, that would imply that a Turing machine can do everything that a human brain can do. Wouldn't that prove the thesis?

# Answer
> 17 votes
How would you prove that the machine is faithfully simulating a brain? How would you prove that it doesn't matter if you simulate my brain or your brain or somebody else's brain?

Church–Turing isn't something that can be proven. It's essentially just the statement that Turing machines correspond to the intuitive notion of algorithm and that just isn't a statement of mathematics. The Turing machine is the definition of computability; Church–Turing is essentially the claim that we picked the right definition, in the sense that choosing any of the reasonable alternative definitions would give exactly the same notion of computability.

# Answer
> 7 votes
Part of the issue with the idea of "proving" the Church-Turing thesis is that the Church-Turing thesis isn't a precise mathematical statement. Rather, it's the idea, or "belief" if you will, that any model of computation that could feasibly be constructed is either equal in power to a Turing machine or weaker than a Turing machine.

If we were to try to formalize the Church-Turing thesis into a rigorous mathematical statement, we'd have to somehow give definitions to terms like "model of computation" or "feasibly constructed" that are, by design, very vague. After all, the whole point of the Church-Turing thesis is to claim that working with Turing machines really captures what computation is because any other model we could have picked would end up equal in power to Turing machines. We can precisely pin down particular rules for what a model of computation is and what it means for it to be feasible to construct, but by doing so we'd limit the resulting theorem to only talking about those classes of machines. If someone later on devises some new model of computation that is wildly different than everything we've ever thought about so far and ends up being more powerful than Turing machines, then the *intuitive* Church-Turing thesis would be false (Turing machines don't actually capture computation!) but the *rigorous* Church-Turing thesis would still be true (because this new model of computation wouldn't fit into the framework developed so far).

Here's another way to see this. There are formal proofs that Turing machines can simulate computers and that computers with unbounded memory can simulate TMs. We have similar results from certain types of cellular automata (Conway's Game of Life, for example), string rewriting systems (unrestricted grammars), crystal structures (see this amazing link), etc. All of these specific cases lend support to the Church-Turing thesis, but none of these statements, in isolation, *is* the Church-Turing thesis.

So suppose that we prove that a TM can simulate the human brain. This would be a *huge* result! But that by itself doesn't prove the Church-Turing thesis because, by nature, the Church-Turing thesis is unprovable. In a sense, the answer to the more general question of "can the Church-Turing thesis be proven?" is "no," so your question falls out as a special case.

That said, it is potentially possible to *disprove* the Church-Turing thesis by finding some model of computation that can solve a number of problems that TMs cannot but at the same time is still something that can be feasibly constructed in the universe. In that sense, the Church-Turing thesis is more of a falsifiable scientific hypothesis than a mathematical theorem.

# Answer
> 4 votes
No, that wouldn't prove the thesis. Human beings are allowed to use machines. For example, an important consequence of the Church-Turing thesis is that computers can only compute Turing-computable functions. It is a statement about the physical universe and its capacity for computation.

# Answer
> 1 votes
No. There's no reason to believe that the human brain includes all parts of physics. In fact we're pretty sure it doesn't include many, like black hole physics and high energy particle collisions. So if black hole physics is uncomputable, that would disprove the physical Church-Turing thesis, but wouldn't prevent you from simulating a human brain.

---
Tags: computability, simulation, church-turing-thesis
---


# Question
Title: Minimum stabbing problem for a set of convex polygons
Let $S = \\{P\_1, P\_2, ..., P\_m\\}$ be a set of convex polygons in $\mathbb R^2$ with a total of $n$ vertices. Polygons are defined by ordered lists of vertices, and each vertex is represented by a pair $(x,y)$ of its Cartesian coordinates. Polygons may have non-empty pairwise intersections.

A convex polygon is called *stabbed* by a line, if there is a non-empty intersection between them. A set $L$ of lines is called *stabbing set* for the set $S$, if each polygon in the $S$ is stabbed by at least one line from the $L$. Find a minimum stabbing set for the set $S$.

Are there any algorithms (papers, research) for this problem?

This problem is related to this question on SO.

# Answer
As others have pointed out, the problem is NP-hard. The best we can expect in this case is an approximation algorithm. Set-Cover is a natural choice for this. But the main hurdle here is that the subsets are not explicitly handed out to us. If we somehow have a subset of all possible stabbings, we immediately have a $O(\log n)$ approximation algorithm via Set-Cover. Just iteratively pick the set covering the largest number of elements that are yet to be covered.

Observe that if there is a line $l$ that stabs a subset of $S$, we can shift/rotate the line so that it still stabs the same set. In the extermal case, we would have a line $l'$ that passes through two vertices of any of the two polygons it stabs. Therefore, we are to only observe $n\choose 2$ such lines, which would give us the required subsets for Set-Cover.
> 1 votes

---
Tags: optimization, computational-geometry, polygons
---


title: Deciding if a language is CFL or in $P$

text:
# Question
Title: Deciding if a language is CFL or in $P$
I'm trying to decide whether $L\_c=${$w=uxu, | \ u,x\in \Sigma ^\* \ and \ |u|=c $} for some constant $c\in \mathbb{N}$ is context free or not.

initialliy, I've thought about choosing $x=\epsilon$ which will lead to $w=uu, \ u\in \Sigma ^\* $ but I've been told that since $c$ is a constant, it wont be the same language as $L=${$uu | u\in \Sigma ^\* $} which put me in a standstill.

I've also thought about some examples that will make the pumping lemma not work on $L\_c$, yet they all seem to fail (I couldent find a pumping constant that throws me out of $L\_c$)

any ideas on how to progress from here?

# Answer
> 2 votes
Observe that for some $c \in \mathbb{N}$ and finite alphabet $\Sigma$, $\Sigma^c$ with $|\Sigma^c| = |\Sigma|^c$ is finite. Therefore

$$L\_c = \bigcup\_{u \in \Sigma^c} u\Sigma^\*u$$

is the union of a finite number of regular languages. So $L\_c$ must be regular/context-free.

---

Assume that $\Sigma$ and $c$ are chosen as above and that $\sim\_c$ is the indistinguishability relation for $L\_c$. By the Myhill-Nerode theorem, $L\_c$ is regular if and only if $\Sigma^\*/\sim\_c$ is finite. We now prove $L\_c$ regular by showing that each string in $\Sigma^\*$ is indistinguishable to one of length $\leq 2c$, so the number of classes in $\Sigma^\*/\sim\_c$ must be bounded by $|\Sigma|^{2c}$.

Choose $w \in \Sigma^\*$, if $|w| \leq c$ then $w \sim\_c w$. If $|w| \> c$ then there must be $u \in \Sigma^c$, $y \in \Sigma^+$ such that $w = uy$. Now take the greatest prefix $u\_1$ of $u$ such that $y = xu\_1$ for some $x \in \Sigma^\*$. If $z \in \Sigma^\*$ with $|z| \geq c$, then

$$wz = uyz \in L\_c \iff u \text{ is a suffix of } z \iff uu\_1z \in L\_c.$$

Because $u\_1$ is the greatest prefix of $u$ with $w = uxu\_1$, it follows that if $|z| \< c$ then also

$$wz = uyz \in L\_c \iff u\_2z = u \text{ for a suffix } u\_2 \text{ of } u\_1 \iff uu\_1z \in L.$$

So $w \sim\_c uu\_1$ and $|uu\_1| \leq |uu| = 2c$, done.

---
Tags: context-free, pumping-lemma
---


# Question
Title: Best internal representation of a random variable to enable iterative sampling and interpolation/regression
Let $\[0,100\]$ denote the interval of real numbers between $0$ and $100$. Given a function $f:\[0,100\]^n \rightarrow \mathbb{R}^+$, I want to implement the following simple algorithm to search for the point in $\[0,100\]^n$ maximizing $f$:

1.- Observe the value of $f$ at $k$ random points chosen uniformly in $\[0,100\]^n$. Let $A$ be the set of these points.

2.- Iterate many times:

* (2.1) Calculate an interpolation function $g$ whose values coincide with those of $f$ for all points in $A$ (alternatively, $g$ could be a regression rather than an interpolation).
* (2.2) Sample $k$ points in $\[0,100\]^n$ in such a way that the probability of choosing each point is proportional to the value of $g$ at them.
* (2.3) Add these sample points to set $A$.

3.- Return the point of $A$ maximizing $f$.

I want to reach some tradeoff between the sophistication of the interpolation made in step (2.1) and the efficiency of the sampling method in step (2.2). What kind of interpolation or regression method should I use to compute function $g$ at each iteration?

On the one hand, the interpolation function $g$ could just return the weighted average of $f$ at all points in $A$, in such a way that the weight of each of these points in the calculation of $g$ at any point $p$ is e.g. inverse proportional with the distance of that point to $p$. In this case, the sampling step (2.2) could use the accept-reject sampling method. However, if $g$ gives extremely low values to many points, then the accept-reject method would have to be repeated a high number of times for each sample.

On the other hand, the interpolation function $g$ could be calculated as an interpolation n-dimension polynomial coinciding with $f$ for all points in $A$. In this case, the sampling step (2.2) would not need to use any try-and-fail method as before. Since polynomials can be integrated, we could do the sampling as follows: we uniformly sample a value $r\in\[0,1\]$ and then calculate the value $x\_0$ of the first variable (i.e. dimension) such that the volume of $g$ for the interval $\[0,x\_0\]$ of the first variable and the intervals $\[0,100\]$ for all other variables is an $r$-proportion of the whole volume for all points in $\[0,100\]^n$ (a trivial integral defines this volume). Then we do the same for the second variable (conditioned to the fact that the value of the first variable is $x\_0$) and so on for all variables, removing a variable each time until we find out all the dimensions of our sampled point. However, I have not found any library letting me perform a multidimension polynomial interpolation for e.g. 30 dimensions or so. A very interesting interpolation library is Minterpy, but computing a high-degree 30-dimension polynomial from any unstructured sample set A is unfeasible. Is there any library letting me do this?

Is there any interpolation or regression library which is suitable for e.g. 30-dimension functions but, at the same time, the interpolated/regression function enables some direct sampling method not based on try-and-fail?

# Answer
> 1 votes
Good ideas! Unfortunately there is no single correct answer to your question. There is a "no free lunch" theorem that says every approach will work better on some functions $f$ and worse on others. So you will need to make a choice that is based on intuition, domain knowledge, or experiments. It might depend on what form you expect the true function to take and the number of dimensions. One approach is to use a neural network as $g$.

You might be interested to read about Bayesian optimization, which is an elaboration/extension of your idea, augmented with some predictions of where $g$ is more accurate and where it is likely less accurate, then using that information as well to help select more points to sample.

You might start by picking an existing Bayesian optimization toolkit/software package and try applying it to your problem setting.

Be prepared that black-box optimization can be extremely hard or extremely easy, depending on the nature of $f$, so you might be in a problem domain that is extremely difficult -- or you might not.

---
Tags: optimization, statistics, polynomials, sampling
---


# Question
Title: Knapsack Problem: Find Top-K Lower Profit Solutions
In the classic 0-1 knapsack problem, I am using the following (dynamic programming) algorithm to construct a "dp table":

```
def knapsack(weights, values, capacity, n):
    n = len(weights)
    weights = np.concatenate(([0], weights))  # Prepend a zero
    values = np.concatenate(([0], values))    # Prepend a zero

    table = np.zeros((n+1, capacity+1), dtype=np.int64)  # The first row/column are zeros
    for i in range(n+1):
        for w in range(capacity+1):
            if i == 0 or w == 0:
                table[i, w] = 0
            elif weights[i] <= w:
                table[i, w] = max(
                    table[i-1, w-weights[i]] + values[i],
                    table[i-1, w]
                )
            else:
                table[i, w] = table[i-1, w]
    return table

```

Then, by traversing the table using the following code, I am then able identify the items that make up the optimal solution:

```
def get_items(weights, capacity, table):
    items = []
    i = len(weights)
    j = capacity
    weights = np.concatenate(([0], weights))  # Prepend a zero
    table_copy = table.copy()
    while i > 0 and j > 0:
        if table_copy[i, j] == table_copy[i-1, j]:
            pass  # Item is excluded
        else:
            items.append(i-1)  # Item is included, fix shifted index due to prepending zero
            j = j - weights[i]
        i = i-1
    return items

```

This is great for finding the items that make up the single optimal solution (i.e., highest total summed value). However, I can't seem to figure out how to retrieve, say, the top-3 or top-5 solutions from this table that has a total weight that is less than or equal to the maximum capacity.

For example, the top-3 solutions for the following input would be:

```
weights = [1,  2,  3, 2, 2]
values =  [6, 10, 12, 6, 5]
capacity = 5

# with corresponding "dp table"
array([[ 0,  0,  0,  0,  0,  0],
       [ 0,  6,  6,  6,  6,  6],
       [ 0,  6, 10, 16, 16, 16],
       [ 0,  6, 10, 16, 18, 22],
       [ 0,  6, 10, 16, 18, 22]])

```

| Total Summed Value | Items (Zero-based Index) |
| --- | --- |
| 22 | 1, 2 |
| 22 | 0, 1, 3 |
| 21 | 0, 1, 4 |

Note that there is a tie for both first place and so we'd truncate the solutions after the first 3 rows (though, getting all ties is preferred if possible). Is there an efficient way to obtain the top-k solutions from the "dp table" via some sort of backtracking process?

# Answer
> 0 votes
Dynamic programming algorithms can often be viewed as a shortest-paths problem on a suitable dag. Then, if you only want the top-1 solution, i.e., the shortest path, you can use prev pointers to find the shortest path. If you want the top-$k$ solutions, you can use any algorithm for finding the $k$ shortest paths in a graph. See, e.g., https://en.wikipedia.org/wiki/K\_shortest\_path\_routing, https://en.wikipedia.org/wiki/Yen%27s\_algorithm, https://stackoverflow.com/q/7208720/781723.

In your code, you have

```
table[i, w] = max(
                    table[i-1, w-weights[i]] + values[i],
                    table[i-1, w]
                )

```

You can think of this as corresponding to a dag where each pair $(i,w)$ corresponds to a vertex in the dag, and I suspect the above expression means that you have an edge from $(i-1,w)$ to $(i,w)$ of length 0 and an edge from $(i-1,w-\text{weights}\[i\])$ to $(i,w)$ of length $-\text{values}\[i\]$. (Why negation? To convert the "max" to a "min".) I'll let you work out the details of how your algorithm can be expressed as a problem of finding a shortest path in a dag.

---
Tags: algorithms, dynamic-programming, knapsack-problems, backtracking
---


# Question
Title: What is the role of diagonalization in the proof of undecidability of the halting problem?
I'm trying to understand the proof of undecidability of the halting problem. Some resources give a short proof based on a proof by contradiction. There is no mention of diagonalization. But some others also mention diagonalization in the proof. I'm rather confused about the role of diagonalization in this proof. Is it needed? If yes what is its role? Or can the proof be done without utilizing diagonalization?

# Answer
Unless you found an unusual proof, they're all refutations by contradiction (not "proofs by contradiction", although that is common parlance) *and* they all are qlso a form of diagonalization: to refute the claim, we assume there were a halting oracle, and derive a contradiction by diagonalizing against the oracle.

You might be getting too hung up with what books *call* these proofs, and whether they bother to mention words "contradiction" and "diagonalization". They should all be the same proof, if we discount minor details in presentation.
> 5 votes

---
Tags: undecidability, halting-problem, diagonalization
---


title: Maximum of a tritonic array

text:
# Question
Title: Maximum of a tritonic array
I have found out how to find the maximum of a "bitonic" array. The problem is as follows.

An array is bitonic if it is comprised of an increasing or decreasing sequence of integers followed immediately by a decreasing or increasing (respectively) sequence of integers. Write a program that, given a bitonic array of n distinct integer values, determines whether a given integer is in the array. Use O(lg n) compares in the worst case.

This can easily be done using a modified binary search.

I was wondering if one could find the maximum of "tritonic" array.

A tritonic array is, naturally, an array with an increasing run of elements, then decreasing, then finally increasing again or decreasing-\>increasing-\>decreasing.

I've tried a similar binary search approach but to no awail.

I would really appreciate some pseudocode or python outlining the algorithm. Specifically, I'm looking for an O(lg n) algorithm.

I am asking about this because I believe this may relate to a problem I'm having implementing Chan's algorithm, which I asked about here.

NOTE: bitonic arrays are also called unimodal and rotated sorted arrays.

EDIT: This paper describes how to find the maximum of a specific bimodal/tritonic array

# Answer
You can't. It's not possible to do this in $O(\log n)$ time.

Consider the following two possibilities for the tritonic array:

1. We have an array $A^1$ that contains the values $1,2,3,4,\dots,n$, except that at index $i$, we have the value $2n$.
2. We have an array $A^2$ that contains the values $1,2,3,4,\dots,n$, except that at index $i$, we have the value $2n+1$.

Intuitively, if the algorithm does not read the $i$th entry in the array, then it cannot distinguish between these two arrays. An algorithm that runs in $O(\log n)$ time can only examine $O(\log n)$ entries of the array. So, the chances that it happens to examine the $i$th entry is vanishingly small ($O((\log n)/n)$, since every other array entry is identical in both arrays and gives no information about $i$ or whether we're dealing with $A^1$ or $A^2$). Consequently, any such algorithm can't be correct most of the time at finding the maximum of the input array.

You can formalize this using an adversary algorithm. Let $A^0$ denote the array that contains the values $1,2,3,\dots,n$. For a deterministic algorithm, we imagine running the algorithm, to find the maximum of the input array $A^0$, examine which entries it reads, then after it completes, pick an index $i$ such that it hasn't read entry $i$ (one must exist: since it runs in $O(\log n)$ time, it examines at most $O(\log n)$ entries, so there must exist some entry that hasn't been examined). We can see that the algorithm must do exactly the same steps and produce the same output, regardless of whether it is run on $A^0$, $A^1$, or $A^2$, since all three arrays are identical on the entries it reads. Now the algorithm must produce the wrong answer on at least one of those inputs. Therefore the algorithm is not correct.

This can be generalized to prove that no randomized algorithm running in $O(\log n)$ time exists, either.
> 1 votes

---
Tags: search-algorithms, search-problem, binary-search
---


# Question
Title: Can the MST's "cut property" be derived from the "cycle property" and vice versa?
The cut and cycle properties of the minimum spanning tree are well-known. It is easy to use similar arguments to prove them. But I wonder if one property be derived from the other.

> Cut property: Suppose edges X are part of an MST of G=(V, E). Pick any subset of nodes S for which X does not cross between S and V-S, and let e be the lightest edge across this partition. Then X + {e} is part of some MST.

> Cycle property: Pick any cycle in the graph, and let e be the heaviest edge in that cycle. Then, there is an MST that does not contain e.

From Dashupta, Papadimitrionu, and Vazirani's Algorithms

# Answer
> 3 votes
The technical answer is that they imply each other. Since they are both true statements either implication evaluates to $T \to T$ which is a true statement. However, I know that you are really asking if you can prove MSTs have the cycle property only using the fact that they have cut property. The answer is no.

We define a *1-tree* to be a connected graph with exactly one cycle. Informally, they are trees plus an edge. Then minimum spanning 1-trees (MS1T) of a graph $G$ satisfy the cut property, but not necessarily the cycle property. Thus the cut property is not enough to prove the cycle property.

Also, the cycle property clearly is not enough to prove the cut property, since the minimum cost acyclic subgraphs (which will always be the graph with no edges whenever all of the edges have positive weights) satisfy the cycle property but not the cut property.

Essentially, the cut property arises from the spanning nature of trees (though not every class of spanning subgraph will satisfy this property) and the cycle property arises from the acyclic nature of trees (though not every class of acyclic subgraph will satisfy this property). Trees are special because they are spanning and acyclic.

---
Tags: minimum-spanning-tree
---


title: Tseitin formula on 2-connected graph

text:
# Question
Title: Tseitin formula on 2-connected graph
How can we prove that for $\\\\\$ every $\\\\\$ 2-connected graph G with an odd number of vertices, the unsatisfiable Tseitin formula for it is minimally unsatisfiable, that is, if we remove even a single clause, it becomes satisfiable?

# Answer
Clearly, whether a formula is minimally unsatisfiable depends on the exact details of how it is formulated, so let me give a specific definition of Tseitin formulas. Given a graph $G=(V,E)$ and a vertex labelling $l\colon V\to\\{0,1\\}$, the CNF $T\_{G,l}$ uses variables $\\{p\_e:e\in E\\}$, and it includes clauses expressing for each vertex $v$ that the parity of its incident edges $\bigoplus\_{e\ni v}p\_e$ is $l(v)$: $$\tag{$C\_{v,\vec c}$}\let\LOR\bigvee\LOR\_{e\ni v}p\_e^{1-c\_e}$$ for each $v\in V$ and each $\\{0,1\\}$-vector $\langle c\_e:e\ni v\rangle$ such that $\bigoplus\_{e\ni v}c\_e=\overline{l(v)}$, where $p\_e^1=p\_e$ and $p\_e^0=\overline{p\_e}$. The formula $T\_{G,l}$ is unsatisfiable if $\bigoplus\_{v\in V}l(v)=1$, because any satisfying assignment would have to satisfy $$1=\bigoplus\_{v\in V}l(v)=\bigoplus\_{v\in V}\bigoplus\_{e\ni v}p\_e=\bigoplus\_{e\in E}\bigoplus\_{v\in e}p\_e=\bigoplus\_{e\in E}0=0.$$

Now, let us try to show that for any given $v$ and $\langle c\_e:e\ni v\rangle$, $T\_{G,l}\let\bez\smallsetminus\bez\\{C\_{v,\vec c}\\}$ is satisfiable. To guide our search, notice that since $T\_{G,l}$ is unsatisfiable, any satisfying assignment of $T\_{G,l}\let\bez\smallsetminus\bez\\{C\_{v,\vec c}\\}$ must refute $C\_{v,\vec c}$, i.e., it must extend the partial assignment $a$ such that $a(p\_e)=c\_e$ for all edges $e$ incident to $v$. But it is easy to see that if we restrict $T\_{G,l}\bez\\{C\_{v,\vec c}\\}$ with $a$, we end up with another Tseitin formula $T\_{G',l'}$, where $G'$ is $G$ with $v$ and all its incident edges deleted, and $$l'(u)=\begin{cases}l(u)\oplus c\_{\\{u,v\\}}&\text{if }\\{u,v\\}\in E,\\ l(u)&\text{otherwise.}\end{cases}$$ Thus, it suffices to show that $T\_{G',l'}$ is satisfiable. Crucially, observe that $$\bigoplus\_{u\ne v}l'(u)=\bigoplus\_{u\ne v}l(u)\oplus\bigoplus\_{e\ni v}c\_e=\bigoplus\_{u\ne v}l(u)\oplus(l(v)\oplus1)=\bigoplus\_{u\in V}l(u)\oplus1=0.$$ Moreover, if we assume $G$ is $2$-connected, then $G'$ is connected. Thus, it remains to prove the following:

> **Lemma.** If $G'=(V',E')$ is connected and $l'\colon V'\to\\{0,1\\}$ satisfies $\bigoplus\_{v\in V'}l'(v)=0$, then $T\_{G',l'}$ is satisfiable.

To prove this, we may assume without loss of generality that $G'$ is a tree (we may take an arbitrary spanning tree of $G'$, which is still connected, and set the remaining edges to $0$). Then the $\mathbb F\_2$-linear system $\\{\bigoplus\_{e\ni v}p\_e=l'(v):v\in V'\\}$ has a unique solution that can be determined by working inwards from the leaves; the condition $\bigoplus\_vl'(v)=0$ ensures that it works out in the root.

In fact, the unique satisfying assignment $a$ has a simple explicit description: any given edge $e$ splits the tree in two trees with vertex sets $V\_0$ and $V\_1$ (that is, $V\_0$ and $V\_1$ are the two components of the graph $(V',E'\bez\\{e\\})$), and we put $$a(p\_e):=\bigoplus\_{v\in V\_0}l'(v)=\bigoplus\_{v\in V\_1}l'(v).$$ To see that $a(T\_{G',l'})=1$, consider any vertex $v\in V'$, let $\\{e\_i:i\<d\\}$ enumerate the edges incident to $v$, and for each $i\<d$, let $V\_i$ be the component of $(V',E'\bez\\{e\_i\\})$ that does not contain $v$. Then by definition, $a(p\_{e\_i})=\bigoplus\_{u\in V\_i}l'(u)$, and $V'\bez\\{v\\}$ is a disjoint union of the sets $V\_i$ for $i\<d$, thus $$0=\bigoplus\_{u\in V'}l'(u)=l'(v)\oplus\bigoplus\_{i\<d}\bigoplus\_{u\in V\_i}l'(u)=l'(v)\oplus\bigoplus\_{i\<d}a(p\_{e\_i}),$$ that is, $\bigoplus\_{e\ni v}a(p\_e)=l'(v)$.
> 4 votes

---
Tags: graphs, satisfiability, propositional-logic, 3-sat, connected-components
---


# Question
Title: Proof that nondeterministic TM runs in exponential time
Consider a nondeterministic TM $M$ that takes as input another TM $M'$, a string $x$ and integer $k$. $M$ decides if there exists a string y s.t. $|y| \leq |x|^2$ and $M'(x, y)$ accepts in $k$ steps. Show that $M$ runs in exponential time.

I don't see why it is exponential time. $M$ guesses $y$ with length $|x|^2$, then verifies by running $M'(x, y)$ in $k$ steps to see if $M'$ accepts, so shouldn't it be polynomial time?

# Answer
> 1 votes
Assuming $k$ is represented in binary, it takes $\lg k$ bits to represent $k$. So an algorithm whose running time is $\Theta(k)$ runs in time that is exponential in the length of the input. "Exponential time" means "exponential in the length of the input".

---
Tags: turing-machines, np, nondeterminism
---


title: Resources on Moore and Mealy Machines

text:
# Question
Title: Resources on Moore and Mealy Machines
I was studying about Moore and Mealy machines but having hard time connecting with them because 1) they are different from typical normal machines.what is the need of "output" and 2) My text book doesn't cover it (Michael Sipser). What are the application for Moore and Mealy machines? I would like some resources.

# Answer
Moore and Mealy machines are often introduced as a tool for designing digital circuits. Nice introductions can be found here and here.
> 3 votes

# Answer
A prominent and interesting application of transducers, among many others, is to define strategies in game theory. To illustrate this, let me show a few kinds of games and how their strategies differ.

First, *reachability games*. We are given a graph. One vertex is marked as the initial vertex, and some vertices are marked as goal vertices. There is a game token, which starts on the initial vertex. Eve plays against Adam. At their turn, each of the two players moves the token from the current vertex to a vertex which is adjacent on the graph. Eve wants to make the token reach a goal vertex.

A *strategy* for a player is a way for that player to choose the next move based on what happened in the game so far. Reachability games are *determined*, meaning that one of the players always has a *winning strategy*, i.e., a strategy which makes them always win. What is more, reachability games are particularly simple because there is always a *positional* (or *memoryless*) winning strategy, i.e., a strategy where the next move only depends on the current state of the game, and not on the past history of the moves. It's not very hard to convince yourself of this fact: essentially, nothing in the future of the game depends on the past of the game, so there is nothing smarter you can do if you remember the whole history of the game, compared to making a decision just based on the vertex where the token is at the current step.

A toy game to illustrate that this isn't always the case: There is a stack of tokens, and at each turn, the current player adds as many tokens to the stack as they want. The goal of Eve is to ensure that after her turn, there is always a prime number of tokens. This is easy to win for Eve, because for every natural number $n$, there is a prime number greater than $n$. What's interesting about this game, though, is that Eve not only needs to remember things about the past of the game, but if she is playing with a program, that program uses unbounded memory, as it needs to store an arbitrarily large integer. This is called an *infinite-memory* strategy.

Finally, let us return to games on graphs. Now, some vertices of the graph have a treasure, which Eve can collect by moving the token to such a vertex. The goal of Alice is to collect as many treasures as possible. This time, Alice cannot play optimally with a positional strategy. For example, suppose that at the first turn, she makes a move in order to go collect some treasure, she manages to collect it in spite of Adam's adverse moves, and Adam gets the token back to the initial vertex. Now, if she does the same thing that she did on the initial vertex at the beginning, she will go looking for the same treasure again, but it's already been collected, so there is nothing to win anymore. It's smarter to go in another direction to hunt for some other treasure. On the other hand, if Eve plays with a program, that program only needs a finite amount of memory, because all that counts from the history is which treasures have been collected so far. This is called a *finite-memory* strategy.

When studying any class of games, an important question (after proving that winning strategies exist at all) is to determine whether there are positional or finite-memory winning strategies. There are results in game theory which quantitatively study the amount of memory needed to play winning strategies in certain sorts of games.

Now, what's the link with transducers, you ask? Saying that a strategy has finite memory comes down to saying that the strategy can be realized with a transducer. The finite memory is represented by a state structure, which has a token (not the same as the game token for graph-based games) that starts in some predefined state, and each move by the opponent (say, Adam, if this is a strategy for Eve) makes the token take a transition in the state structure. The output of the Moore/Mealy machine at each step is the move that the strategy tells Eve to take.

For more about this topic, see the textbook Games on Graphs coordinated by Nathanaël Fijalkow. Memory is defined in section 1.5.

Another example of a game for which winning strategies are finite-memory but usually not positional is the game associated with a non-deterministic Büchi automaton, where Eve chooses successive letters of an infinite word, Adam chooses the transitions to take in the automaton (when there are several choices because of non-determinism), and Eve's goal is to construct a word which is accepted by the automaton with its non-deterministic power, but which Adam doesn't manage to make accepted by choosing transitions as the letters come. This gives rise to the notion of *good-for-games automata*, which has been widely investigated by research in recent years.
> 4 votes

---
Tags: finite-automata
---


# Question
Title: How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?
I'm attempting to solve the recurrence relation:

$$ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $$

in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the Master's Theorem. We know that if $O(n^{2-\epsilon}) = \frac{n}{\lg n}$ is correct, then $T(n) = \Theta(n^2)$. However, is this correct? And how can I demonstrate it?

# Answer
If you want to see it explicitly here is the calculation:

$T(n)=4T\left(\frac{n}{2}\right) + \frac{n}{\log n}$ implies that the total number of recursions we do is $\log\_2 n$. At the pass of the recursion $i$, we have $4^iT\left(\frac{n}{2^i}\right)$ plus all the other terms deriving by the non-recursive term given by $\sum\_{j=1}^i 4^{j-1}\frac{n/2^{j-1}}{\log(n/2^{j-1})}$.

Putting all together and assuming that the recursion for $n=1$ is $T(1)=c=O(1)$, we have:

$$T(n)=c\cdot 4^{\log\_2 n} + \sum\_{i=0}^{(\log\_2 n) -1} 4^i \cdot \frac{n/2^{i}}{\log(n/2^{i})} \ .$$ Simplifying $4^{\log\_2 n}$ as $n^2$ and the fractions inside the summation, we obtain:

$$T(n) = c \\, n^2 + n \cdot \sum\_{i=0}^{(\log\_2 n) -1} \frac{2^i}{\log(n/2^{i})} \ .$$

We can now conclude with a double inequality:

* From one side, it is obvious that $T(n)\geq n^2$, so we have $T(n)=\Omega(n^2)$.
* On the other hand, we have, from the formula above, that: $$T(n) \ \leq \ c \\, n^2 + n\cdot \sum\_{i=0}^{(\log\_2 n) -1} 2^i \ = \ c \\, n^2 + n\cdot\bigl( 2^{\log\_2 n} -1 \bigr) \\ \ = \ c \\, n^2 + n(n-1) \ \leq \ c \\, n^2 + n^2 = (c+1)n^2 \ .$$ With this, we can conclude also that $T(n)=O(n^2)$.

Finally, we have $T(n)=\Theta(n^2)$.
> 2 votes

---
Tags: time-complexity, asymptotics, recurrence-relation, recursion
---


# Question
Title: How does additional assumptions increase approximation factor?
I am studying the greedy algorithm for maximal weighted matching in arbitrary graphs. I have proven that this algorithm has approximation factor $\frac{1}{2}$.

Assume now that the weights in the graph are such that if $W = ⟨w\_1, w\_2, \ldots , w\_{|E|}⟩$ is the weights sorted in increasing order, then $w\_i \leq cw\_{i+1}$ for all $i \in \\{1, 2,\ldots , |E| − 1\\}$ with $0 \< c \leq 1$. I believe that the approximation factor should increase when $c$ gets smaller, and I would like to express the approximation factor as a function of $c$. I have tried finding the approximation factor when $c = \frac{3}{4}$ but have not done much progress.

Any help would be very much appreciated:)

# Answer
I guess that greedy approach should consider edges in weight decreasing order only.

> Otherwise it may become much less optimal, getting approximation factor as low as $c^{2n/3}$.

Then every edge $e\_0$ of greedy matching may block up to two edges $e\_1$ and $e\_2$ of maximum weight matching. However since $e\_0$ is taken by greedy approach, then $w(e\_0) \> w(e\_1)$ and $w(e\_0) \> w(e\_2)$. WLOG $w(e\_1) \> w(e\_2)$, then $w(e\_1) \le c w(e\_0)$ and $w(e\_2) \le c w(e\_1) \le c^2 w(e\_0)$. Therefore maximum weight of a matching is at most $\max\\{\\,1, c + c^2\\,\\}$ times greater than the weight of greedy matching. So the approximation factor is $\frac{1}{\max\\{\\,1, c + c^2\\,\\}} = \min\\{\\,1, \frac{1}{c + c^2}\\,\\}$. For $c = \frac 34$ it equals to $\frac{16}{21}$. Note that for $c \le \frac{\sqrt{5} - 1}2$ greedy approach gives an optimal solution.
> 2 votes

---
Tags: graphs, greedy-algorithms, matching
---


# Question
Title: Is limiting the input type in subclasses legitimate (does it give a stronger or the same specification)?
Note: I have read a similar post, but my problem seems different from that. Read **my attempts to understand the problem** for why I believe they are different.

# My problem:

I know that (see this and this)

> 1. A subtype of another type should give stronger or the same specifications of the supertype.
> 2. Spec $A$ is stronger than spec $B$ iff the set of implementations that satisfy $A$ is a proper subset of the set of those that satisfy $B$. Therefore, $A$ is stronger than $B$ if either
>     * i. $A$ has weaker preconditions than $B$ does, or
>     * ii. $A$ has stronger postconditions than $B$ does.

However, I have encountered a confusing situation in today's programming:

* I have a base class `Essay`, and subclasses of different kinds of essays, say `EssayA` and `EssayB`, that inherit `Essay`.
* To summarise a list of a specific kind of essay, I define the base class `EssaySummariser` that
    + has a virtual method `include(Essay e)` that takes an essay into account for the future summary.
        - `include()`'s precondition: e must all be of a certain type of `Essay`.
        - `include()`'s postcondition: e is included in the summariser and will be used to form the summary.
    + has a virtual method `summarise()` that summarises all included essays.
* Now to implement a summariser for essays of type A, `EssayA`, I define a subclass of `EssaySummariser`, `EssayASummariser`, which overrides the `include()` method:
    + new `include()`'s precondition: e must all be of the type `EssayA`
    + new `include()`'s postcondition: e is included in the summariser and will be used to form.

**It appears that `EssayASummariser`'s spec of `include()` has a stronger precondition than `EssaySummariser`'s. However, it also doesn't seem wrong as a subtype.**

# My attempts to understand the problem

1. I have attempted to treat the new specification as having the same precondition but as having a stronger postcondition: only e's of type A are included. Other types will cause the method to throw.

* This attempt to interpret it seems wrong, because the new postcondition I imagined violates the original one (original one says any type of e's will be included)
2. I have just read a similar post here. Trying to apply the answer to that post, I may imagine that my `EssaySummariser` is not a true ADT, but `EssayASummariser` is.

* However, the situation in my problem here is different from that in that post. Specifically, my `EssaySummariser` is not a genetic type.
    * More seriously, if the two situations are the same, then I imagine I can convert genetic classes in that problem to non-genetic classes in my problem, and say that some classes cannot be ADT because of such specifications. This does not sound right because I think any specs can be allowed into an ADT.

# My questions

1. Is it legitimate to create subtypes like I did in my problem? In particular, was my attempt 2 correct in applying that post's knowledge to my problem?
2. If it is, how do I map the theories to the reality in the problem?

# Answer
I'm not an expert on this, but with the way you have defined `EssayASummarizer`, I don't believe it is a subtype of `EssaySummarizer`. You have already explained why: the set of implementations that can instantiate `EssayASummarizer` is not a subset of the set of implementations that can instantiate `EssaySummarizer`. Specifically, an instance of `EssayASummarizer` has an `include()` method that cannot accept an `EssayB`, so it does not qualify as an instance of `EssaySummarizer`.

I suggest you read more about covariance and contravariance, e.g., https://en.wikipedia.org/wiki/Covariance\_and\_contravariance\_(computer\_science). Your `EssaySummarizer` is like a function `Essay` -\> `Output`, and your `EssayASummarizer` is like a function `EssayA` -\> `Output`. The latter function is not a subtype of the former function, due to contravariance of the type of the input to the function.
> 3 votes

---
Tags: type-theory, abstract-data-types
---