# Question
Title: Algorithm for animating/morphing convex polygon diagrams
I am trying to find an algorithm to smoothly morph a (given) diagram made of convex polygons into another (given) diagram of the same type.

The target diagram is usually generated from the source, where all kind of operations may happen (new polygon popping up, polygon gets deleted etc.)

So for example I may want to go from  To

with the following constraints:

* Morphing between the two diagrams should be smooth (e.g: new polygons should not pop up but kind of grow)
* In all intermediate diagrams the polygons should be simple and convex

I tried looking around for papers and/or previous work on that, but failed spectacularly in finding anything, so...

Does anyone here have any idea/references?

(Heck, I'm not even sure this is the right stack exchange board to ask for it)

# Answer
> 2 votes
If your initial set of polygons is a power-diagram, you can insert a new polygon by inserting a new center and growing its power circle smoothly. You don't have direct control of the polygons but rather of the underlying power circles. Power diagrams as Voronoi diagrams are always made of convex polygons.
https://diglib.eg.org/bitstream/handle/10.2312/evs20201057/109-113.pdf

Another way is to subdivide one of the polygons slicing it with a straight line, similar to a spatial partition tree, to ensure the resulting polygon is still convex. http://proceedings.mlr.press/v84/fan18b/fan18b.pdf

---
Tags: algorithms, computational-geometry
---


# Question
Title: Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma
I am trying to show that $A = \\{w \in \\{a,b,c,d\\}^{\*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\\}$ is not regular by using the Pumping Lemma.

My idea here was to use the string $ s = (ab)^{p}(cd)^{p} $. Clearly, $ s \in A $, and $ |s| = 2p \geq A $. So the the three conditions of the pumping lemma hold.

Where I am stuck is picking the correct decomposition of $ s $. My idea was to do the following:

We can decompose $ s $ into $ xyz $ such that:

* $ x = (ab)^{j}, j \geq 0 $
* $ y = (ab)^{k}, k \geq 1 $
* $ z = (ab)^{p-j-k}(cd)^{p} $

Now consider if we "pumped" $ y $. Let $ i = 2 $. Then $ xy^{2}x = (ab)^{j}(ab)^{2k}(ab)^{p-j-k}(cd)^{p} = (ab)^{p+k}(cd)^{p} \notin A $. Therefore, we arrived at a contradiction and $ A $ is not a regular language.

But my confusion here is that the $ xyz $ I have chosen is not the only decomposition of $ s $. For example, you could choose $ x = a $, $ y = b $, and $ z $ is the rest of the string. Do I have to cover all possible cases? If so, this seems like a bad choice for $ s $ -- any other ideas?

Another concern is that my chosen decomposition violates the condition $ |xy| \leq P $ of the Pumping Lemma will not hold for $ p = 1 $.

# Answer
> 2 votes
Ok I will split the answer into two parts, one for each of your questions \ concerns \ confusions:

---

Q: Are we allowed to use the pumping lemma if we chose a specific decomposition, or do we need to show for all decompositions?

A: The pumping lemma states, $\exists p.\forall w.|w|\ge p \rightarrow \exists x,y,z.w=xyz \land\text{ they are a valid decomposition }\land\forall k\in\mathbb{N}.xy^kz\in A$.

and you are trying to show the negation of this statement. as you can see, there is an "exists" sign before the "x,y,z" and therefore in the negation there will be a "for all" sign.

Thus, you **MUST** go over **ALL** possible decompositions in order to use the pumping lemma in this way.

---

Q: This doesn't work for $p=1$ but works for every other value of $p$. is this a problem?

A: no! its absolutely fine.

Say, for example, you know how to prove for $p=5$ and you don't know how to do $p=1$. define $w=(ab)^5(cd)^5$, and you know that $|w|\ge 5 \ge 1=p$. but since $|w|\ge 5$ and you know how to solve for $p=5$, you know how to deal with $w$.

This means that its enough to prove for some value of $p$ and all other values BELOW it will be automatically proved too!

---

Also, you are in the right direction. This is a good choice of a word, but you will need to work a bit more to show that every decomposition cannot be always pumped.

I hope this helped you a bit :)

# Answer
> 1 votes
You need to consider *all* possible decompositions. There aren't so many cases to consider:

1. $x \in (ab)^\*$, $y \in (ab)^+$.
2. $x \in (ab)^\*$, $y \in (ab)^\*a$.
3. $x \in (ab)^\*a$, $y \in (ba)^+$.
4. $x \in (ab)^\*a$, $y \in (ba)^\*b$.

Go over them one by one.

---
Tags: regular-languages, finite-automata, pumping-lemma
---


# Question
Title: What is the requirement for bubble sort to complete in 1 pass?
I am working on a problem where you're given $n$ distinct numbers, and you want to find the number of permutations such that it takes bubble sort at most 1 pass to complete.

e.g., if `n=3`, then the following permutations would only require 1 pass

```
1 2 3
1 3 2
3 1 2
2 1 3

```

But

```
3 2 1
2 3 1

```

would require more than 1 pass. Apparently the answer is $2^{n - 1}$, but I am not sure how to prove this for the general $n$ case.

My question is, what are the general constraints for a sequence to allow for it to be sorted with 1 pass of bubble sort?

It is difficult for me to come up with a generic formula to generate the permutations for larger $n$.

# Answer
> 2 votes
I'm assuming that a pass of bubble sort on the array $A\[1\],\ldots,A\[n\]$ proceeds as follows:

* If $A\[1\] \> A\[2\]$ then swap $A\[1\]$ and $A\[2\]$.
* If $A\[2\] \> A\[3\]$ then swap $A\[2\]$ and $A\[3\]$.
* ...
* If $A\[n-1\] \> A\[n\]$ then swap $A\[n-1\]$ and $A\[n\]$.

Bubble sort halts after a pass in which no swaps were made.

As is evident, if bubble sort halts after one pass, then the array must have been sorted.

When does bubble sort halt after two passes? If after the first pass, the array is sorted. In this case, if we know which swaps were made, then we can recover the input permutation. Furthermore, different sets of swaps correspond to different initial permutations. It follows that there are $2^{n-1}-1$ permutations that cause bubble sort to halt after exactly two passes. Together with the identity permutation, it follows that there are $2^{n-1}$ permutations that cause bubble sort to halt within two passes.

How do these permutations look like? Suppose that the first $k$ swaps are made, and then the following swap isn't made. Since the first $k$ swaps are made but the following one isn't made, at the end of the pass the first $k+1$ elements of the array will be $A\[2\],\ldots,A\[k+1\],A\[1\]$, which must correspond to the permutation $1,\ldots,k+1$. Hence the original permutation started $k+1,1,\ldots,k$.

From here, it's not too difficult to describe all $2^{n-1}$ permutations. Starting with the identity permutation, partition it in an arbitrary way, and rotate each part one step to the right. For example, when $n = 3$ we get:

* $1|2|3 \to 1|2|3$.
* $1|23 \to 1|32$.
* $12|3 \to 21|3$.
* $123 \to 312$.

Each division in the partition corresponds to a step in the pass during which there was no swap.

---

Here is another way of describing these permutations: they avoid the patterns $231$ and $321$. This means that for any $i\<j\<k$, it cannot be that $A\[k\] \< A\[i\],A\[j\]$. To prove this, we show that any permutation above satisfies this constraint, and then prove the converse.

Consider any of the $2^{n-1}$ permutations above, and let $i\<j\<k$. Since each element in a part is smaller than each element in a subsequent part, $A\[k\] \< A\[i\]$ is only possible if $i,j,k$ are all in the same part. Moreover, $A\[k\] \< A\[j\]$ for indices $j\<k$ in the same part only if $j$ is the first element in the part, which is impossible since $j\>i$.

Suppose now that we are given a $(231,321)$-avoiding permutation. Let $i$ be any index such that $A\[i\] \> i$. All elements in $i,\ldots,A\[i\]-1$ must appear before all elements in $A\[i\]+1,\ldots,n$, since otherwise there will be a copy of $231$. Furthermore, the former must appear in increasing order, since otherwise there will be a copy of $321$. Therefore the part of the array that follows $A\[i\]$ is $A\[i\],i,i+1,\ldots,A\[i\]-1$.

Imagine now scanning the array in the order $A\[1\],A\[2\],\ldots$. The first time that $A\[i\] \neq i$, necessarily $A\[i\] \> i$ (since we've already seen all smaller elements), and so the following elements are $i,\ldots,A\[i\]-1$. When we continue the scan, again the first time that $A\[i\] \neq i$ we must have $A\[i\] \> i$ (since we've already seen all smaller elements), and so on. Therefore the array is of the form above.

# Answer
> 1 votes
Bubble sort isn’t completed when the array is sorted - it is completed when we *know* the array is sorted.

Take the case 1-3-2. We have x-y-z and bubblesort figures out in the first pass that x is less than y and y is greater than z. It doesn’t know how x and z are related and therefore doesn’t know whether the array is sorted after one pass or not, therefore bubblesort is not complete at this point

If you change the question to “how many passes until the array is sorted”, that’s a different question. But to answer the question: If the number of array elements is zero or one, then bubble sort completes with zero passes. Otherwise, if either the array is sorted or the array has two elements then bubble sort complets with one pass. Otherwise, two or more passes are needed.

---
Tags: sorting
---


# Question
Title: Algorithm for assigning people to groups
> Given a list $L = \[1, 2, .., n\]$ and a list $C = \[(L\_i, L\_j), ....\]$ form a group of pairs $G = g\_1, ..., g\_{n/2}$ such that:
>
> 1. every element of $L$ is assigned to exactly **one** group
> 2. $g\_k = (L\_i, L\_j) \Rightarrow (L\_i, L\_j) \notin C $ (constraint)

I get that there are (potentially) many solutions to this problem. How can one construct a **recursive** algorithm $group(L, C)$ to that returns a possible grouping?

I get that you can: 1) Create all pairs from $L$ and 2) Create all possible groups of size $n/2$ from the pairs and select one group that is legal.

I see that there are $N\_P = {N\choose 2} = \frac{n!}{2!(n-2)!}$ potential pairs in $L$. The number of groups is then ${N\_P\choose N/2} = \frac{N\_P}{(N/2)!(N\_P-N/2)!}$

Then one has to go through all these groups and check if it is legal and return it if so.

Any other solutions?

# Answer
> 3 votes
# This problem is equivalent to Perfect Matching

We can view the input as an almost-complete graph, with L as its vertices and every two vertices connected by an edge except for those in C. We then want to find a set of edges that uses every vertex exactly once. This is the perfect matching problem.

To solve this problem, you can use any algorithm for finding a maximal matching, and check if the maximal matching has $n/2$ matches.

---
Tags: algorithms, np-hard, recursion, assignment-problem
---


# Question
Title: Examples of difficult Hamiltonian Cycle Problems
I am working on implementing algorithms to solve Hamiltonian Cycle Problem. I need difficult problem graphs to test my implementations but my google-fu is weak and am unable to find any.

Please advise where I might find a set of difficult graphs for the Hamiltonian Cycle, or how to generate such graphs for testing.

# Answer
TSPLIB contains some instances of Hamiltonian Cycle. Haythorpe \[1\] proposes a set of around a thousand instances which are claimed to be "structurally difficult" (not necessarily large).

---

Haythorpe, Michael. "FHCP Challenge Set: The first set of structurally difficult instances of the Hamiltonian cycle problem." arXiv preprint arXiv:1902.10352 (2019).
> 3 votes

---
Tags: hamiltonian-path, data-sets, hamiltonian-circuit
---


# Question
Title: how to find all negative weight cycles(elementary circuit) in a strongly connected directed graph?
I can use Bellman-Ford to get some of the elementary negative weight cycles in a graph. It's not guaranteed to always get all of them.

(Elementary Cycle: A cycle is elementary if no vertex but the first and last appears twice.)

But I want to find *ALL* elementary negative weight cycles. Even taking each vertex as the source will not always get *ALL* negative weight cycles.

Take this graph for example:

With Bellman-Ford, starting from any vertex, I can only get one cycle "U→H→U".

The cycle "U→S→U" is always missing.

Is there any algorithm with which I can find all negative weight cycles reliably?

# Answer
> 1 votes
My current strategy is:

1. first enumerate all elementary cycles. I use the hawick algorithm which is already implemented in the c++ boost library.
2. sum all the weights of edges in each cycle and then check if the sum is negative.

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Distribution of random Fourier coefficients
Let $f : \\{0, 1\\}^{n} \rightarrow \\{-1, 1\\}$ be a Boolean function. Let the Fourier coefficients of this function be given by

$$ \hat f(z) = \frac{1}{2^{n}} \sum\_{x \in \\{0, 1\\}^{n}} f(x)(-1)^{x \cdot z}$$

for each $z \in \\{0, 1\\}^{n}$, where $x \cdot z$ is the bitwise inner product between $x$ and $z$. Let me choose a function uniformly at random from the set of all Boolean functions $$\\{f : \\{0, 1\\}^{n} \rightarrow \\{-1, 1\\}\\}. $$

What is the distribution that each Fourier coefficient $\hat f(z)$ is distributed as?

# Answer
> 2 votes
Each Fourier coefficient on its own is the average of $2^n$ independent uniformly random $\pm1$ variables. Its distribution is roughly normal with mean $0$ and variance $2^{-n}$.

---
Tags: probability-theory, boolean-algebra, fourier-transform
---


# Question
Title: What is the expected time complexity of checking equality of two arbitrary strings?
The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters.

So far so good. I think we can all agree that checking equality of two *equal length* strings requires O(n) runtime.

However many (most?) languages (I'm using Python 3.7) store the lengths of strings to allow for constant time lookups. So in the case of two *unequal length* strings, you can simply verify `len(string_1) != len(string_2)` in constant time. You can verify that Python 3 does indeed make this optimization.

Now, if we're checking the equality of two *truly* arbitrary strings (of arbitrary length) then it is much more likely (infinitely, I believe) that the strings will be of unequal length than of equal length. Which (statistically) ensures we can nearly always compare them in constant time.

So we can compare two arbitrary strings at O(1) average, with a very rare worst-case of O(n). Should we consider strings comparisons then to be O(1) in the same way we consider hash table lookups to be O(1)?

# Answer
> 3 votes
In order to discuss the expected time complexity of an operation, you have to specify a distribution on the inputs, and also explain what you mean by $n$.

One has to be careful, however. For example, consider the suggestion in the comments, to consider some kind of distribution over words of length at most 20. In this case, string comparison is clearly $O(1)$, since 20 is just a constant. There are several ways to avoid it:

* Ask for a non-asymptotic time complexity. Since time complexity is highly dependent on the computation model, you can count (for example) the number of input memory cells accessed.
* You can specify an input distribution which depends on a parameter $m$, and then ask for the asymptotic complexity in terms of $m$.

Here is an example. Given two random binary strings of length $n$, there will be roughly 4 accesses in expectation. In contrast, if the strings are chosen at random from the collection $0^i1^{n-i}$, the number of accesses will be roughly $(2/3)n$. These two distributions can be separated even if we use asymptotic notation: the algorithm runs in $O(1)$ on the first distribution, and in $\Theta(n)$ on the second.

Another issue is the meaning of $n$. Consider for example a string $0^m$, where $m \sim G(1/2)$ is a geometric random variable. When run on inputs of lengths $a,b$, the running time is $\Theta(\min(a,b))$. How should we express this in terms of $n = a+b$? One choice is to ask for the expected running time given that the input length is $n$. In this case, $$ \mathbb{E}\[\min(a,b)\] = \sum\_{a=1}^{n-1} \frac{(1/2)^a (1/2)^{n-1-a}}{\sum\_{a'=1}^{n-1} (1/2)^{a'} (1/2)^{n-1-a'}} \min(a,n-a) = \frac{1}{n-1} \sum\_{a=1}^{n-1} \min(a,n-a) \approx \frac{n}{4}, $$ so the expected running time is $\Theta(n)$.

# Answer
> 1 votes
In addition to what was said before, consider a modern version of "string" that is fully Unicode compatible. Which means a string is a sequence of Unicode code points, and you can't just compare whether code points are equal, because there are cases where a letter can be represented in different ways, sometimes in many different ways. As an example, the code point sequences (c with cedilla, accent), (c, cedilla, accent) and (c, accent, cedilla) compare equal with a correct implementation.

# Answer
> 0 votes
In Addition to what have been said, and independently on the test if the size is equal or not, let's be the following:

1. Let be two strings of same length `m` over an alphabet $\sigma$.
2. Let $w$ be the word memory. From wikipedia : a word is a fixed-sized piece of data handled as a unit by the instruction set or the hardware of the processor. In Theory, if we have $n$ elements (in random-access machine (RAM) model), the word length $w =\Omega(log n)$:

* Each character needs $log \sigma$ bits.
* $m$ characters need $m log \sigma$ bits
* To compare two strings of length $m$ we need $m log \sigma / w$ which gives us $O(m log \sigma / w)$.

**Clarification**:
Normally (and Naively), we check one char at the time, which gives $O(m)$.
Using advantage of Bit-level parallelism, the processor can handle a data of size $w$ at single time, this, mean to check m characters we need $m/w$ operations.
Example from wikipedia:
*For example, consider a case where an **8-bit processor must add two 16-bit integers**.The processor must first add the 8 lower-order bits from each integer, then add the 8 higher-order bits, **requiring two instructions** to complete a single operation. A **16-bit processor** would be able to complete the operation with **single instruction**.*

**In practice**, An illustrating example:

* in $64$ bits machine
* using C language, where `sizeof(char) = 1 Byte` which is $8 bits$
* For $m = 8$ characters, which means $8\times8 = 64$ bites

Here, naively, if we check each char alone , we need *8 operations*. If we take advantage of Bit-level\_parallelism, where the processor can handle 64 bits at the time, so we need only *one operation* ($ len(str)\*size\\\_char\\\_bits / w\\\_in\\\_bits = 8 chars * 8 bits / 64 bits = 1$)

**important note**: this is just to check if the two string are equal or not.

Edit one info: Correct some mistakes. Thank you @greybeard, for your valuable comment.

---
Tags: time-complexity, runtime-analysis, python, string-matching
---


title: A language that is not context free

text:
# Question
Title: A language that is not context free
I working through some textbook exercises, and came across a problem that I'm struggling with.

Give a CFL $L$ such that $\\{x|\forall y \in \Sigma^\* \space xy \in L\\}$ is not a CFL.

I've got the idea that we can let $L$ be formed by taking a language that is not CFL, and following each element by every string, and also add in the prefixes of elements of the non CFL language. But I'm not sure how to find a language such as this that is a CFL. However, I'm struggling to think of an example with such a property.

Any help would be appreciated.

# Answer
For simplicity, let us define that if $L$ is some language, $pref(L)$ to be the described language generated from $L$ (do not not to be confused with the language prefix operator)

Let us also define $\Sigma = \\{a,b,c,e\\}$.

We know that the language $L=\\{a^nb^nc^n|n\in\mathbb N\\}$ is not CFL, so we may want to use it.

Lets think in terms of your idea: we will want some other language $\hat L$ where $pref(\hat L)$ is similar to $L$ itself.

First, notice that simply applying your idea is not very useful: we may start with a word $aaabbbccc\in L$ and after we add to its the $y$ at the end, we can find ourselves with the word $aaabbbccccccccccccc\in \hat L$. This will make everything much harder to do, as this word could as well end up in $pref(\hat L)$ (think why!) and therefore in this case $pref(\hat L)$ is not very similar to $L$.

So how do we fix it? We can just add a new letter that will seperate our words in $L$ from the rest. This letter will be $e$ (short for "end") - so our new definition for $L$ would be as follows: $L=\\{a^nb^nc^ne|n\in\mathbb N\\}$. **Now**, if we would have taken a look at $\hat L = L\Sigma^\*$ (concatenation of those two languages) we would have $pref(\hat L)=\hat L$ but also $\hat L$ is very similar to $L$ in its core structure (and also is not a CFL for the same reason $L$ isn't).

Now we have a different problem, since $pref(\hat L)=\hat L$ we obviously can't have $\hat L$ being a CFL with $pref(\hat L)$ not a CFL. To fix this, we need a key observation: if we add some arbitrary word to $\hat L$, for example the word $ababa$ \- then since it wasn't in $L$ already, it won't be in $pref(\hat L)$ too! (find a $y\in \Sigma^\*$ where this word concatenation with $y$ is not in $\hat L$)

This means, we may somehow be able to add things to $\hat L$ while keeping $pref(\hat L)$ the same (and not a CFL). Adding all words of the form $we$ where $w\in\Sigma^\*\setminus\\{e\\}$ with $|w|=3n$ for some $n\in\mathbb N$ should do the trick, but I will leave proving that $pref(\hat L)$ didnt change with those additions. Notice now that this language not is CFL, but its also regular! the automata that solves this language is simple: it checks whether the first occurrence of the letter $e$ is in a position that is a multiple of 3.

So finally, the language $\hat L=\\{a^nb^nc^ne|n\in\mathbb N\\}\Sigma^\*\bigcup \\{we|w\in\Sigma^\*\setminus\\{e\\}\land \exists n\in\mathbb N .|w|=3n\\}$ is regular (and hence a CFL) while $pref(\hat L)=\\{a^nb^nc^ne|n\in\mathbb N\\}\Sigma^\*$ is not a CFL.

---

Sorry if this post was too long! I hope it helped you understand the problem and its solution on all of their steps and thinking methods.
> 1 votes

---
Tags: automata, context-free, computation-models
---


# Question
Title: Is realization of unit disk graphs hard?
It is known that recognizing a unit disk graph is NP-hard \[1\].

However, the paper does not mention how hard the realization problem is.

I have looked up several references \[2\]\[3\]\[4\]. None of the papers answer whether the following problem is NP-hard:

> Given a unit disk graph $G = (V,E)$, find a configuration of a set $\mathcal{D}$ of disks, such that the intersection graph $G(\mathcal{D})$ of $\mathcal{D}$ is isomorphic to $G$.

The difference between this problem and the recognition problem is that the input of this problem is guaranteed to be a unit disk.

Is there any study that shows the complexity of the above problem? I expect it to be NP-hard, but I am yet to find a full proof.

# Answer
One of the complications here is that there is no natural "decision variant" of this problem, since this isn't an optimization problem. (and the problem "given an UDG, is there a realization?" is trivial)

Since reductions between decision problems tend to be better studied, one option is to make it an optimisation problem in a chosen parameter. Even though you don't care about that value, you can use binary search on the optimisation problem to solve the realisation problem. Hence, the realisation problem is not much easier than the opt. problem, so showing the opt. problem is hard suffices.

The question then of course is what parameter to choose. Perhaps the problem "Given an UDG, find a realisation with minimum/maximum sum of edge lengths" would be suitable. It seems related to the problem that Aspnes et al. \[1\] show to be NP-hard.

---

\[1\]: ASPNES, James, et al. A theory of network localization. IEEE Transactions on Mobile Computing, 2006, 5.12: 1663-1678.
> 2 votes

# Answer
If there would be a polynomial time algorithm for your problem, it could be used to solve the NP-hard recognition problem in polynomial time by just giving the input to it and checking if its output is correct. Therefore the problem you pose is NP-hard in the sense that if it admits polynomial time algorithm, then P=NP.

(Here we assume that the input is some well-known encoding of a graph, and therefore the restriction that the input must be an unit disk graph doesn't really make the problem at all easier. Maybe there could be some other encodings in which only unit disk graphs could be represented, but formulating them would be another topic.)

---

Edit: I'll try to formalize the question and the answer more:

Formalization of the question: Is there a Turing machine $M$ and a polynomial $p(n)$, such that if the input of $M$ is a unit disk graph $G$ with $n$ vertices encoded as an adjacency matrix, then $M$ terminates in at most $p(n)$ steps, and outputs an unit disk configuration of $G$? In particular, the machine $M$ is allowed to have undefined behavior if the input is not an unit disk graph encoded as adjacency matrix.

Answer: Suppose that there is such Turing machine $M$ and polynomial $p(n)$. Now, we can solve unit disk recognition problem in polynomial time as follows: Given a graph $G$ with $n$ vertices, run $M$ with $G$ as input for $p(n)$ steps. If $M$ does not terminate in $p(n)$ steps, output NO. If $M$ terminates, test if the output of $M$ is an unit disk configuration of $G$. If it is, output YES and otherwise NO. Now we have solved an NP-hard problem in polynomial time, so we have a contradiction if we assume $P \neq NP$.
> 2 votes

---
Tags: reference-request, computational-geometry, np-hard
---


# Question
Title: If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?
This question boils down to: **If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor?**

Let's take the Traveling Salesman Problem for example:

> **TSP Decision Problem (NP-Complete):**
> Input: Graph G, Budget b
> Output: Does a route exist in G with a distance of at most b? (true/false)

> **TSP Optimization Problem (NP-Hard):**
> Input: Graph G
> Output: What route in G has the shortest distance?

If one could find a polynomial time solution for the TSP Decision Problem wouldn't they also have a polynomial time solution for the TSP Optimization Problem?

> Why? Binary search.

You can run your polynomial time solution for the TSP Decision Problem on G over and over with an input for b that increases, e.g. {1, 2, 4, 8, 16, 32, 64, 128, 256, ...}, until the algorithm returns false. Then you decrease b and slowly hone in on the correct answer.

Is this logic correct?

# Answer
In this particular example, the following works: Let $A$ be the algorithm for deciding whether some graph $G$ has a TSP-route has a cost of at most $b$. We start by finding the optimal $b^\ast$ using $A$ and binary search on an appropriate range (say $\[0, \sum\_{e \in E(G)} w(e)\]$) in polynomial time.

Following this, we start modifying the instance graph $G$ by setting edge weights to some large value so they will *never* be picked (e.g. $1 + b^\ast$) in a route of optimal cost $b^\ast$ and using $A$, we check whether the resulting graph still has a route of cost $b^\ast$. If that is the case, we keep the modification and otherwise we undo it. However, we now know that *any* such route (in the modified graph) must include the edge we messed with, so we store that. Successively applying this to all edges we will find at least one such edge per pass over $E(G)$ and after at most $|V(G)|$ passes, we will have found a TSP-route of cost $b^\ast$ consisting of the edges we stored.

Hence we call $A$ an polynomial ($O(|V(G)| \cdot |E(G)|)$, or if you want $O(|V(G)|^3$) amount of times (in the second step, the first one also takes polynomially many) and all of our other operations can also be easily done in polynomial time.

Therefore, we can solve the optimization problem in polynomial time if we have a polynomial-time algorithm for the decision variant.

This approach also works for other problems (with slight variations for the second part); in fact I am not aware of a problem where this general strategy fails. I am actually pretty sure that one can use it to recover an accepting path of a polynomially-bounded NTM which can then be used to solve optimization variants of all $\mathsf{NP}$-complete problems.
> 2 votes

---
Tags: optimization, np-complete, np-hard, np, decision-problem
---


title: Bottleneck TSP with repeated nodes

text:
# Question
Title: Bottleneck TSP with repeated nodes
I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also NP-hard. However, I was not able to find a reference for the complexity of the bottleneck TSP problem with repeated nodes for complete graphs.

Also, I am curious if continuously removing the most costly edges until all nodes are not strongly connected actually solves this problem. I think that this method should solve this problem, but I was not sure about it.

# Answer
The problem is in P.

You can solve the decision problem in $O(n^2)$ time, where $n$ is the number of vertices (i.e., linear time in the size of the input). Delete all edge whose weight is above the bottleneck threshold. Form the strongly connected components of the resulting graph, and examine its metagraph. The original decision problem has a bottleneck TSP iff the metagraph is a simple path, i.e., it has the form $w\_1 \to w\_2 \to \dots \to w\_k$ where $w\_1,\dots,w\_k$ are the components and the only edges are $w\_i \to w\_{i+1}$.

You can solve the optimization problem in $O(n^2 \log n)$ time. Sort the set of edge weights, and remove duplicates. Then, use binary search on this set of weights to find the smallest bottleneck threshold such that the decision problem has a solution. You will do $O(\lg n)$ iterations, and each iteration runs the decision problem above, so the total running time is $O(n^2 \lg n)$.
> 0 votes

---
Tags: complexity-theory, graphs, reference-request, combinatorics, traveling-salesman
---


# Question
Title: Are these production rules for a formal grammar?
I have a question on if production rules of a formal grammar are being specified correctly. Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states each rule has the form:

$(\Sigma \cup N)^{\*}N(\Sigma \cup N)^{\*} \implies (\Sigma \cup N)^{\*}$

How can each rule have this form when each rule is a subset of the above arguments to the implication symbol? Should quantification and the $\in$ symbol be used to specify each rule? Thanks

# Answer
> 1 votes
The use of notation in that statement might be confusing. A grammar is a rule of the form "something $\to$ something", where the something on the left is a string of symbols containing at least one non-terminal symbol, and the something on the right is a string of symbols.

For instance, $A \to BcD$ would be a valid rule, as would $AB \to BDeeF$, or $aAcE \to b$.

If you read the very next sentence after the one you quoted, it explains the meaning of the part you didn't understand, in different words. It says "That is, \[...\]" (you can read the rest yourself). If you don't understand one sentence, in the future I suggest you keep reading a little further to see if you can work it out from context.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: What is a good reference for NP hardness in the machine learning/optimization/operations research context?
I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:

> Theorem 1.1. For any constant ϵ \> 0, it is NP-hard to find a halfspace that correctly labels (1/2 + ϵ)-fraction of given examples over {0, 1} n even when there exists a monomial that agrees with a (1 − ϵ)-fraction of the examples. https://people.eecs.berkeley.edu/~prasad/Files/mono.pdf

At this point, the definition of NP-hard is not even defined. I have seen many examples like this, which makes me wonder

"Do all these thousands of authors have the same definition of NP-hard/complexity notions"?

"These contexts seem so different from the usual contexts where NP-hardness come up such as graph coloring or traveling salesman problem, how can I be sure that these notions of complexity/NP hardness are equivalent?"

Can someone point out a good reference for studying complexity theory in a machine learning/operation research/optimization context? Many thanks!

# Answer
> 2 votes
In modern papers, and unless stated otherwise, NP-hardness is one of the following:

* A decision problem is NP-hard if it is NP-hard with respect to many-one reductions.
* An optimization problem is NP-hard if its decision version is NP-hard.

Sometimes, more informal notions are used. The most common one is probably *hardness of approximation*. When a theorem states that maximization problem X is NP-hard to approximate within a factor of $\alpha \< 1$, it usually means that there is a many-one reduction from SAT (or some other NP-complete problem) an instance of X and a parameter $k$ such that

* If the original SAT instance is satisfiable, then the value of the X-instance is at least $k$.
* If the original SAT instance is unsatisfiable, then the value of the X-instance is at most $\alpha k$.

However, to be sure, you need to look at the exact statement being proved.

Your case is similar. The complete version of your paper proves the main theorem in Section 5. Theorem 5.2 on page 21 states exactly what holds in the Yes case and what holds in the No case (Theorem 5.1 shows that it is NP-hard to distinguish the two cases). You should be able to relate this to the informal statement appearing in Theorem 1.1.

---
Tags: terminology, machine-learning, reference-request, np-hard, np
---


title: doubts on cin and scanf

text:
# Question
Title: doubts on cin and scanf
i spent literally 5hrs trying to figure out, why the value of n is 1 for my second test case ( which begins at line 12 ) , but i am unable to, could you help me with that?

```
    int t,n,i,j;
    char c;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<n<<"\n";
        getchar();
        while(scanf("%c %d %d\n",&c,&i,&j)==3)
        {
            cout<<c<<" "<<i<<" "<<j<<"\n";
        }
        getchar();
    }

```

test case:- first line represents the number of test cases, and each test case has a blank line.

```
2

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5

2
q 1 1
c 1 1
q 1 1

```

output :-

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5
1

```
</code></pre>

# Answer
> 0 votes
Your code probably fails because of your use of `scanf(...) == 3`, or because of your use of `getchar()`.

Consider this alternative instead:

```
#include <iostream>

int main() {
  int num_tests;
  std::cin >> num_tests;

  for (int k = 0; k < num_tests; ++k) {
    int n;
    std::cin >> n;
    std::cout << n << "\n";

    std::cin.ignore(1, '\n');

    std::string buf;
    while (getline(std::cin, buf)) {
      if (buf.empty())
        break;

      char c;
      int i, j;
      sscanf(buf.c_str(), "%c %d %d\n", &c, &i, &j);
      std::cout << c << " " << i << " " << j << "\n";
    }
  }
}

```

For clarity, prefer naming your variables in a clearer way and using for loops. Also, never use the identifiers `i` or `j` for anything other than looping.

---
Tags: programming-languages, c, c++
---


# Question
Title: How do Context Sensitive Grammar systems work?
**The Quest**: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result such as 'aaaaabbbbbccccc'.

**What I (think I) understand so far**:

* CDG == CSG (context sensitive grammar)
* Linear bounded automata are a form of Turing machine
* Pushdown automata are related in function to a computing stack
* CSG uses linear bounded automata to find and replace portions of text or language
* The above automata result in stacks that should be worked through sort of like code
* Steps in the stack are called productions
* A production is basically a substitution rule
* Productions go opposite the expected direction, pasting the text after the arrow in place of the text before the arrow
* The automata apparently iterate through until the first step is met, and then works through the automata stack until it is done

**What I know I do NOT understand**:
(I don't expect these questions to be answered - they are only included for detail why I can't seem to solve The Quest)

1. Is the stack iterated over to produce multiple repetitions?

For example, having some programming experience I expect that to produce a result for The Quest I could start with abc and end with aaaabbbbcccc by creating \[if ... then\] style statements like:

```
 a → aa
 b → bb
 c → cc

```

If starting with {abc} then the above might produce {aabbcc}, iterated again to produce {aaabbbccc}, and again to produce {aaaabbbbcccc}
2. Can production replacements happen while skipping above productions? In the above attempted solution, I would not expect to skip a step or do them out of order, but steps 3 and 4 on the wiki appear to be doing exactly that.
3. Can infinite loops result? In comparing the above example to the wiki example, it would seem to me that completing the first step would cause an infinite loop in which 'a' repeats indefinitely because the first 'a' is converted to 'aa', then the second 'a' that now exists needs the rule to be applied and so on resulting in a → aaaaa∞.

I have been researching for hours, and all searches thus far have resulted in only complicated answers that assume I already have a deep understanding of language processing. I find it ironic that Chomsky's system for describing how language works is apparently so difficult to communicate.

In short, I need programmer syntax to explain how automata stacks should be laid out in order to solve The Quest. Thank you for reading.

# Answer
> 1 votes
Producing sentences from a formal grammar does not require a Linear Bounded Automaton (LBA) and does not use a stack. LBAs are an interesting field of investigation but in terms of this question they are mostly a distraction.

Generative or formal grammars do not actually need much in the way of specialised knowledge to understand, at least in terms of what they do. They are a simple game of symbols, in which you start with a single "start symbol" and then repeatedly apply productions (in any order) until you can no longer find an applicable production. A production is applied by finding its left-hand side in the current string, and replacing that with its right-hand side. That's it.

A formal grammar is slightly more than a set of productions, as the above cited Wikipedia link mentions. It also includes the start symbol, as noted, which precisely defines the starting point, and it also divides symbols into two disjoint sets: terminals and non-terminals. Every production must have at least one non-terminal on its left-hand side, which means that if you reach a string with only terminals, no production can be applied and the replacement sequence terminates. (That's why they are called terminals.) A string containing only terminals is called a "sentence" and the language generated by a grammar is the set of sentences which can be produced.

Strings which are generated which are not sentences -- that is, strings which still contain at least one non-terminal -- are called "sentential forms". Not all sentential forms have an applicable production; such a string is a dead-end.

Grammars are essentially non-deterministic. At every step in the above process (called a "derivation"), there may be a multitude of possible applicable productions, in which case (in theory, at least) all of them are applied in parallel (in parallel universes, that is). This makes it difficult -- actually, impossible -- to know, in general, which sentences can actually be generated by a grammar, but by placing restrictions on the possible productions, we can produce sets of grammars which are more tractable.

One possible restriction is to require that the production's left-hand side "key" non-terminal be surrounded by a prefix and suffix which are also prefix and suffix of the production's right-hand side, which must contain something between the prefix and the suffix. (The prefix and suffix might also contain non-terminals, but unless the production's left-hand and right-hand sides are identical, it's always clear which non-terminal is being replaced by such a rule.) Such a rule is called "context-sensitive" because it conditions the replacement on the context in which the non-terminal symbol appears.

Because the replacement in a context-sensitive rule must contain at least one symbol between the prefix and the suffix, the replaced string must be at least as long as the original, so the derivation must be monotonically non-shrinking. That makes it possible to enumerate the sentences produced by the grammar, using a breadth-first search. In fact, we could use the "non-shrinking" rule as a restriction instead of the context-sensitive restriction; we wouldn't end up with the same set of grammars but we would end up with the same set of possible languages. Because non-shrinking grammars are usually easier to come up with than strictly context-sensitive grammars, some people prefer to use this restriction, even as a definition of what a CSG is. (However, that clouds the meaning of "context".)

An even more drastic restriction is to insist that every left-hand side consist of exactly one non-terminal. Such a grammar is "context-free", because a non-terminal can be replaced regardless of what comes before and after it. Context-free grammars are much easier to deal with; they can be mechanically parsed in somewhat reasonable time (that is, less time than the exponential task of generating all sentences of the correct length and checking if the target sentence is one of them). But many interesting languages, including $a^nb^nc^n$, have no context-free grammar.

Hopefully, that's enough background to understand the example grammar and derivation provided in the Wikipedia article context-sensitive grammars, which shows a grammar which produces $a^nb^nc^n$ and illustrates how $aaabbbccc$ is produced by it. The same process can be used to produce a sentence of any length, simply by iterating rule 2 more often before applying rule 1 and then proceeding to the application of the remaining rules.

# Answer
> 1 votes
Your understanding of Linear Bounded Automata is incorrect. These automata are NOT derived from Pushdown Automata - there is no 'stack' in them. A closer understanding would be that LBA are a special, 'truncated' form of Turing Machine, in which the size of the tape is restricted to being linearly-proportional to the size of the input string (actually, with a large enough alphabet, the tape space can be limited to -just- the space taken by the input string).

Also, the grammar-expansion behavior described in (1) is more closely analogous to a *Lindenmyer System*, which is not quite the same as a CSG (in which only one substitution takes place at any one step, so (3) isn't a concern).

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


# Question
Title: What does this language notation specify?
I am given this exercise:

Let **L1 ={akbk : k \> 0}** and **L2={ck : k \> 0}**. For each of the following strings wi, state and explain whether or not wi ∈ L1L2.

w1

w2=aabbcc

w3=abbccw

w4=aabbcccc

w5=ccaabb

w6=ab

So far I haven't seen such a notation for languages as the one that L1 and L2 are seen in. For example, I had seen other notations such as: `L1={w∈{a,b}∗: every a in w is immediately preceded and followed by a b}` which I could understand. A parallel between the two notations will be much appreciated.

Moreover, what does it refer by L1L2? Is this counted as a union or a concatenation?

What I could figure out from this exercise is what w1 is surely not in L1L2, as k must be over 1. Following the same logic, the other answer would be w2 as k will always be the same in both L1 and L2, hence the number of a's, b's and c's shouldn't differ.

Is the above thought correct or is it more to this notation than I have already thought of?

# Answer
Language concatenation is defined as follows: $$ L\_1 L\_2 = \\{ w\_1 w\_2 : w\_1 \in L\_1, w\_2 \in L\_2 \\}. $$ In other words, a word $w$ belongs to $L\_1 L\_2$ if it can be written as the concatenation of two words, $w\_1 \in L\_1$ and $w\_2 \in L\_2$.

This definition should suffice for solving the exercise.
> 3 votes

# Answer
> So far I haven't seen such a notation for languages as the one that L1 and L2 are seen in. For example, I had seen other notations such as: L1={w∈{a,b}∗: every a in w is immediately preceded and followed by a b} which I could understand. A parallel between the two notations will be much appreciated.

Exponents in alphabet symbols denote quantities. They are just a way to simplify/synthesize the more verbose definitions that you mentioned.

> Moreover, what does it refer by L1L2? Is this counted as a union or a concatenation?

$L\_1L\_2$ means concatenation.

> What I could figure out from this exercise is what w1 is surely not in L1L2, as k must be over 1. Following the same logic, the other answer would be w2 as k will always be the same in both L1 and L2, hence the number of a's, b's and c's shouldn't differ.

The $k$s for $L\_1$ and $L\_2$ are two different constraints, so, the quantities of `a`s and `b`s are not related to the quantity of `c`s. The concatenation of these two languages could be defined like:

$$ L = \\{a^kb^kc^i: k \> 0, i \> 0 \\} $$
> 2 votes

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


# Question
Title: Big O notation for Average case in Linear search
Average case complexity for linear search is (n+1)/2 i.e, half the size of input n.

The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given below:

Minimum number of comparisons = 1

Maximum number of comparisons = n

If the element not found then maximum number of comparison = n

Therefore, average number of comparisons = (n + 1)/2

Hence the average case efficiency will be expressed as O (n).(I've seen this in many websites...)

Here, how can we say it as O(n) in big O notation or terminology. It should be O(n/2), I suppose. Kindly clarify me

# Answer
Let us recall the definition of big-O notation. If a function g(n) = O(f(n)), this implies that there exists two positive constants n0 and c, such that for all n \> n0, 0 ≤ g(n) ≤ c f(n)

Hence, it follows that O(n) is equivalent to O(n/2), as n is just n/2 multiplied by a constant factor, which in this case is 2.
> 3 votes

# Answer
Let the probability that the key is found be $p$. Then

* in case of a miss (probability $1-p$), we perform $n$ comparisons,
* in case of a hit (probability $p$), we perform from $1$ to $n$ comparisons with equal probability.

Hence the expected number of comparisons is

$$(1-p)n+\frac{n+1}2p=\frac{(2-p)n+p}2.$$

In Landau's asymptotic notation, this is $\Theta(n)$.
> 1 votes

# Answer
So most of the time we generally disregard constants in complexity analysis, and hence we say that the base doesn't matter. Always remember, whenever we are going for any kind of asymptotic notation we must consider the highest value of 'n'. Big-oh (i.e., $\mathcal{O}$) does not deal with the constant factor (i.e, here it is $\frac{1}{2}$). The constant factor associated with 'n' changes the slope of the curve only. However, $\mathcal{O}$ notation does not deal with this slope of the curve, it deals only with the shape/nature of the curve. This is why $\mathcal{O}(\frac{n}{2})\equiv \mathcal{O} (n)$ . Please give an upvote to my answer if you satisfy with this. Thank you.

\*** Newly Inserted\**

Big-oh notation defines the upper boundary of the function. It does not deal with the slope of the function, it works only the shape of the curve. For example suppose, $Y=mx+c$, is a straight line equation, now for any value of $m$ it will be a straight line, for different value of $m$ we will get the only different slope. But, Big-oh doest not deal with the slope of the function. meanwhile, we must remember that growth of the function concept while addressing the Big-oh. this is an asymptotic notation to express the time complexity. For more details please follow the book "Introduction to Algorithms", written by Thomas H. Coreman, please see the Chapter "Growth of the functions".
> 1 votes

# Answer
My 2 cents (Please, accept my apologies, native English speakers - I will be grateful for stylistic corrections).

Firstly let me say, that when pointing minimum (**best case**) and maximum number (**worst case**) of comparisons as $1$ and $n$ and using "therefore" average is $\frac{n+1}{2}$ leaves impression, that you calculate arithmetical mean, which is wrong action.

Based on above, firstly, I introduce conception of **average case**: suppose we are considering some algorithm and define $T$ its running time or time complexity function as number of some particular operations, depending on input with size $n$. Suppose $T$ can obtain only finite amount of values $x\_1,x\_2,\cdots,x\_k$ and for each value we know also its expectation i.e. we have numbers $p\_1,p\_2,\cdots,p\_k$, where each $p\_i$ characterizing expectation for $T$ to take value $x\_i$. Not going deeply in soul of term "expectation", on first step, we can simply understand them as numbers with properties $\forall i,0 \leqslant p\_i \leqslant 1$ and $\sum\limits\_{i=1}^{k}p\_i=1$ i.e shares, parts of unit. Now average case we define as: $$AT=\sum\limits\_{i=1}^{k}p\_ix\_i$$

In most simple case we can consider equal expectations i.e. $\forall i, p\_i=\frac{1}{k}$ and call it uniform expectation. Not uniform expectations, sometimes, are, also, very useful and interesting.

Now coming back to linear search algorithm, let's assume, that we have array with length $n$ and we are searching for some particular value. Usually we consider $T$ as number of comparisons happened during searching. Obviously we have $n$ possible cases to find searched value respectively on places $1,2,\cdots,n$ or not find it at all, so we have $n+1$ possible cases altogether. Obviously $T$ get value $i$ if find happens on place $i$ and together with case to find happened on $n$-th $T$ get value $n$ also in case when search failed. So we have for $T$ $$\begin{cases} \ \ 1\quad 2 \quad\cdots \quad n \quad n & \text{ values}\\ \ \frac{1}{n+1}\ \frac{1}{n+1} \cdots \ \frac{1}{n+1} \ \frac{1}{n+1} & \text{ expectations} \end{cases}$$ Now average case is $$AT=\sum\limits\_{i=1}^{n}\frac{i}{n+1}+\frac{n}{n+1}=\frac{1}{n+1}\frac{n(n+1)}{2}+\frac{n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$$ Now come time to remember definition of big-$O$ $$O(f)=\\{g: \exists C\>0, \exists N \in \mathbb{N}, \forall n\>N, g(n) \leqslant Cf(n)\\}$$ and we can conclude $$AT=\frac{n}{2}+O(1)=O\left(\frac{n}{2}\right)=O(n)$$ And now we come to your last question and let me show, that $O\left(\frac{n}{2}\right)=O(n)$ i.e. $O\left(\frac{n}{2}\right) \subset O(n)$ and $O(n) \subset O\left(\frac{n}{2}\right)$:

1. Suppose $f \in O\left(\frac{n}{2}\right)$, which means $\exists C,N$ such that $f(n) \leqslant C\frac{n}{2}=\frac{C}{2}n=C\_1 n$, so $f \in O(n)$.
2. Suppose $f \in O(n)$. This means $\exists C,N$ such that $f(n) \leqslant C n=2C \frac{n}{2} = C\_1 \frac{n}{2} $ , so $f \in O\left(\frac{n}{2}\right)$.

**Gift 1**. This gift I would recommend read after understanding above fully. Now let's consider not uniform case, so lets assume that we expect to find searched value with expectation $p$, i.e. find it in any place from $1$ to $n$, and, so, not to find it with expectation $1-p$. Now we have for for $T$ $$\begin{cases} \ \ 1\quad 2 \quad\cdots \quad n \quad n & \text{ values} \\ \ \frac{p}{n}\quad \frac{p}{n}\quad \cdots \ \ \frac{p}{n} \quad \ 1-p & \text{ expectations} \end{cases}$$ Now average will be: $$AT=\sum\limits\_{i=1}^{n}\frac{ip}{n}+n(1-p)=\frac{p}{n}\frac{n(n+1)}{2}+n(1-p)=n\left(1- \frac{p}{2}\right)+\frac{p}{2} = O(n)$$

**Gift 2**. There can be considered linear search algorithm, which counts 2 comparisons on each step, based on counts as a comparison with the desired value, so a comparison when the end of the cycle is checked. In this case is very interesting so called sentinel method of searching. The average of this algorithm is half of the considered classical search. An interesting exercise to test your awareness of the issue.
> 1 votes

# Answer
Review the definition of O(n). The average runtime is:

* $f(x) = O(n) = O(0.5n)$ average time or as sometimes written, $f(x) \in O(n)$. By definition this means, there is some number k so that $\lim\_{x\to\infty} \frac{f(x)}{n}\leq{k}$
* $f(x) = \Theta(n) = \Theta(0.5n)$ average time or as sometimes written, $f(x) \in \Theta(n)$. By definition this means, there is some number k so that $\lim\_{x\to\infty}\frac{f(x)}{n}=k$
* $f(x) {\sim} 0.5n$ average time. By definition this means, $\lim\_{x\to\infty} \frac{f(x)}{n}=1$
> 0 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Transform grammar to Chomsky Normal Form
**Question**:

S → abSab | baSba | TT

T → aTa| bTb | ε

**My answer:** Eliminate ε rules:

S-\> abSab | baSba | TT | T

T-\> aTa | bTb | aa | bb

**Correct answer:**

S → abSab | baSba | TT | abab | baba | T

T → aTa | bTb | aa | bb

I want to know why **abab** and **baba** in S.

For me, ε could be replaced by T so that S-\> abSab | baSba | TT | T

# Answer
I am not really sure what you are asking in your question, but here is the complete transformation into Chomsky-Normal-Form. The provided solution seems to be wrong, if they are really trying to get rid of the $\varepsilon$.

**Step 1. Eliminate $\varepsilon$-rules**

Every occurrence of $T$ could be $\varepsilon$, so like you already stated in your question the result is the following. Note however that $\varepsilon$ itself is part of the language, so even though you are eliminating $\varepsilon$-rules, $\varepsilon$ itself should appear in the production rules.

$S \to abSab \mid baSba \mid TT \mid T \mid \varepsilon,\\ T \to aTa \mid aa \mid bTb \mid bb$

**Step 2. Eliminate chain rules (rules of the form $A \to B$, $B \to \mathrm{expression}$)**

$S \to abSab \mid baSba \mid TT \mid aTa \mid aa \mid bTb \mid bb \mid \varepsilon,\\ T \to aTa \mid aa \mid bTb \mid bb$

**Step 3. Replace terminals (except if there is only one terminal on the right hand side)**

$S \to T\_aT\_bST\_aT\_b \mid T\_bT\_aST\_bT\_a \mid TT \mid T\_aTT\_a \mid T\_aT\_a \mid T\_bTT\_b \mid T\_bT\_b \mid \varepsilon,\\ T \to T\_aTT\_a \mid T\_aT\_a \mid T\_bTT\_b \mid T\_bT\_b,\\ T\_a \to a,\\ T\_b \to b$

**Step 4. Shorten rules**

$S \to T\_a \mid T\_bH\_2 \mid TT \mid T\_aH\_3 \mid T\_aT\_a \mid T\_bH\_4 \mid T\_bT\_b \mid \varepsilon,\\ T \to T\_aH\_3 \mid T\_aT\_a \mid T\_bH\_4 \mid T\_bT\_b,\\ T\_a \to a,\\ T\_b \to b,\\ H\_1 \to T\_bH\_{11},\\ H\_{11} \to SH\_{12},\\ H\_{12} \to T\_aT\_b,\\ H\_2 \to T\_aH\_{21},\\ H\_{21} \to SH\_{22},\\ H\_{22} \to T\_bT\_a,\\ H\_3 \to TT\_a,\\ H\_4 \to TT\_b\\ $
> 0 votes

---
Tags: context-free, formal-grammars
---


# Question
Title: Upper bound on size of minimal binary coverage code
Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X\_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X\_n$ such that every $x \in \mathscr X\_n$ is within Hamming distance $\le r$ of some $y \in S$. A minimal $r$-coverage code is one for which the cardinality $|S|$ is minimal. Let this minimal cardinality be $N\_n(r)$. Note that we have the trivial bound $N\_n(r) \le 2^n$.

> **Question.** What are good upper-bounds for $N\_n(r)$ in terms of $N$ and $r$ ?

# Answer
> 1 votes
So, according to **Theorem 4.3** of this monograph by Réné Struik, if we consider $q$-ary binary codes of length $n$, such that $n \to \infty$ with $r/n \to p \in \[0,(q-1)/q\]$, then the minimal code size has the following asymptotic limit $$ (1/n)\log\_q N\_{n,q}(r) \to 1-H\_q(p), $$ where $H\_q(p)$ is the $q$-ary entropy of $p$. This answers my specific problem which corresponds to $q=2$.

---
Tags: combinatorics, information-theory, error-correcting-codes, entropy, string-metrics
---


# Question
Title: Finding maximum of $n$ many $m$-bit integers
Suppose you want to determine the largest number in an $n$-element set $X = (x\_1, x\_2, \dots , x\_{n})$, where each element $x\_i$ is an integer between $1$ and $2^m − 1$. Describe an algorithm that solves this problem in $O(n + m)$ steps, where at each step, your algorithm compares one of the elements $x\_i$ with a constant. In particular, your algorithm must never actually compare two elements of $X$!

My thoughts: I thought about making intervals $\[1,2), \[2,4), \[4,8), \dots , \[2^{m-1}, 2^m)$ and somehow associate comparisons with these ranges. But, all of them were in vain. Would be welcome to hear your ideas on solving this!

# Answer
Hi I make this post because this question is quite challenging for me and I want to know if my solution will pass "peer-review". Consider following algorithm for a RAM machine (// denotes integer division):

**algorithm ArrayMax**
*Input*: array $A$ of size $n$; $A\[i\] \in \[1,2^m-1\]$
*Output*: $max(A)$

```
left  <- 1
right <- 1
max   <- A[0]
while right <= A[0]: right <- 2*right
left <- right // 2
for i = 1...n-1:
    if A[i] <= left:
        continue
    if A[i] >= right:
        max <- A[i]
        while right <= A[i]: right <- 2*right
        left <- right//2
        continue
    while left-right > 1:
        mid <- (left+right)//2
        if max < mid:
            right <- mid
        else:
            left <- mid
        if A[i] < left:
            break
        else if A[i] >= right:
            max <- A[i]
            delta <- right-left
            left  <- right
            right <- left+delta
            break
return max

```

The algorithm operates by keeping $left \leq max \< right$ and uses the bounds to make comparisons. Notice that if the bounds of $max$ aren't sufficient they are extended via binary search. How can one proof that this algorithm runs in $O(n+m)$? (This is not a rigorous proof; more an idea; if you have improvements please edit or write a comment)

I'll try to outline a proof using a potential function $\Phi(S\_i)$ ($S\_i$ is the state of the algorithm at iteration $i$). The Potential Method is usually used for data structures. We define: $$\Phi(S\_i) = \log2(left-right) \geq 0$$ There are two things that can happen between $S\_i$ and $S\_{i+1}$ (We only consider the worst case so we'll ignore the first "if" in the loop and focus on the second "if" and the while loop). If the second "if" is triggered the following change occurs in the potential function: $$\Phi(S\_i) = j \rightarrow \Phi(S\_{i+1}) \approx \log2(A\[i\]))$$ Also the cost of the operation is $T\_i \approx \log2(A\[i\]) - \log2(right) \leq \log2(A\[i\]) - \log2(max)$ In the second case a binary search occurs which goes to depth $k$ (does $k$ bisections). $$\Phi(S\_i) = j \rightarrow \Phi(S\_{i+1}) \approx j-k$$ Notice that the cost of bisecting is roughly $4\*k$ comparisons. Thus the cost including the Potential Function is: $$T\_i = O(1) + 4k + 4(\Phi(S\_{i+1})-\Phi(S\_i)) = O(1) + 4k - 4k = O(1)$$ So basically the second case is for free. Lets now focus one the first case only. Consider that it happens $h$ times in a row. It is easy to see that for the second case to not occur $A\[i+1\] \geq 2A\[i\]$ Meaning we can approximate the cumulative cost with: $$\sum\_{i=1}^h \log2(2^{i+1}) - \log2(2^i) + (\Phi(S\_{i+1})-\Phi(S\_i)) = \sum\_{i=1}^h 2(\log2(2^{i+1}) - \log2(2^i)) = \sum\_{i=1}^h2(i+1-i) = 2h$$ Notice that since the the numbers are limited by $2^m$ we have $h \leq m$. Thus we obtain $O(m + n)$, where $m$ is accounting for the first cases and n is accounting for the second cases. Also the first while loop finding bounds for $A\[0\]$ runs at most $m$ times. I hope you get my idea, despite the fuzzy argument.
> 1 votes

---
Tags: algorithms, comparison
---


# Question
Title: Polynomial time algorithm for finding a maximal monotone subset
**Input:** Some fixed $k\>1$, vectors $x\_i,y\_i\in\mathbb R^k$ for $1\le i\le n$.

**Output:** A subset $I\subset\\{1,\dots,n\\}$ of maximal size such that $(x\_i-x\_j)^T(y\_i-y\_j) \ge 0$ for all $i,j\in I$.

**Question:** Can this be computed in polynomial time in $n$?

**Remarks:**

* For $k=1$ this is equivalent to the problem of finding a longest increasing subsequence. Indeed, assuming that $x\_1\<\dots\<x\_n$, we search for a longest increasing subsequence of $y\_1,\dots,y\_n$. Such a subsequence can be found in $O(n\log n)$.
* The problem is related to the notion of a *monotone operator* $F:\mathbb R^k\to\mathbb R^k$. Monotonicity of $F$ means that $(x\_1-x\_2)^T(F(x\_1)-F(x\_2))\ge 0$ for all $x\_1,x\_2\in\mathbb R^k$.
* The problem can be formulated as a search for a maximum clique in the graph $G=(V,E)$ with vertices $V=\\{1,\dots,n\\}$ and edges $E = \\{(i,j) \\;:\\; (x\_i-x\_j)^T(y\_i-y\_j)\ge 0 \\}$. The general clique problem is NP-complete. However, it might be possible to exploit the special structure of $E$ (as shown in the first remark, this is possible when $k=1$).

I would appreciate any hint or comment on this problem.

# Answer
> 0 votes
I stared at this a while now with $k=2$ and got nowhere.

* Let's take on $k=2$. To avoid confusion with x and y coordinates, I'll call the vectors $a\_i, b\_i$ instead.
* Lets define $D(i,j)=(a\_j-a\_i)^T(b\_j-b\_i) \ge 0$, and $R(i,j)$ to be the boolean relation which holds when $D(i,j)\ge0$.
* For $k=1$, R was a total ordering, which is what let us find increasing subsequences. For $k=2$, it's not even a partial ordering, which makes me think any solution will not resemble the $k=1$ case.
    + Take $x\_1,x\_2,x\_3=(0,0),(0,1),(1,0)$; $y\_1, y\_2, y\_3=(0,0), (-6, 1), (-5,-5)$
    + $V(1,2)=1$; $V(2,3)=1$; $V(1,3)=-10$

I'd suggest checking if this can be reduced to the longest common subsequence problem (I suspect no, because of the lack of ordering) or to/from some form of linear programming.

To nitpick here, coordinates should really be taken from $\mathbb Z$ bounded by some reasonable (say, polynomial) function for CS problems, not "$\mathbb R$". I suspect you can show it's NP-complete otherwise, say by reduction to the longest common subsequence problem, but in some way that's not really related to whatever your real problem is. That said, I didn't succeed at actually doing so.

---
Tags: algorithms, graphs, np-complete, subsequences
---


# Question
Title: What are the options of head movement for a Turing machine?
I find several contradictory definitions regarding the head movements of the Turing machine. In some places, it is only L / R. While in some other formal definition; it is L / S / R. Which one is correct?

# Answer
You are right to be confused! The problem is that different authors disagree on the definition of a Turing machine. There is actually no one "right" answer. Some authors define that the machine moves L / R; but others define that it moves L / S / R, as you have pointed out.

This is not the only thing that different definitions of a Turing machine disagree on. For example, some authors say that a Turing machine has a "halt" state, and some say that it has an "accept" and a "reject" state. Additionally, some authors say that a Turing machine's tape is "doubly infinite", meaning that it extends to infinity in both directions. But other authors say that a Turing machine's tape is "singly infinite", meaning that it only extends to infinity in one direction, and in the other direction it stops.

So what should you do about this? Well...

* **If you are a student or learning from a book:** take a look at your textbook to see which definition they use. That definition is the "correct" one for the purposes of working through specific exercises.
* **If you are trying to understand the "bigger picture":** then realize that it actually doesn't matter which definition you use! It turns out that all the different definitions are equivalent. So, which definition is picked is more a matter of convention, kind of like how we choose to say that $1$ is not a prime number, even though historically many mathematicians said that it was.
* **If you a researcher:** Just pick whichever one is convenient to you or makes sense to you, and stick to it, and make sure you are consistent within your own paper or writing material to always use the same definition.

> Which one is correct?

To reiterate: neither is correct; they are just different conventions. It doesn't really matter which you pick, because it turns out they are all equivalent.
> 20 votes

# Answer
As explained, the two formalisms are equivalent, as well as many other variations of Turing machine formalisms, so in a sense it doesn't matter.

But, if you want to 'program' a Turing machine, if you are using a single-tape machine, I guess having S is okay but kinda pointless: at some point you should move your head, so why don't you do that right now?

On the other hand, if you are using a multi-tape machine, having S could be useful: you can do something on one tape, while other heads on other tapes remain stationary.
> 0 votes

---
Tags: turing-machines, automata
---


# Question
Title: Optimising an exhaustive search for a card game
I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an analogue for the rest of the question. For the few who benefit from this information: the game I'm referring to is Magic The Gathering, and the problem is finding whether or not a set of lands can cast a given card.

We can think of the materials as steel and wood. Any resource produces a combination of them. For example:

```
Requirement: 1 steel + 2 wood
Resources:
- 1 steel + 1 wood
- 1 wood
Verdict: POSSIBLE

```

There may be generic requirements, which can be fulfilled by whatever resource is available.

```
Requirement: 2 ANY + 1 wood
Resources:
- 1 steel
- 1 wood
- 1 wood
Verdict: POSSIBLE

```

Resources may be used to produce different combinations at will, when stated of course.

```
Requirement: 1 steel + 1 wood
Resources:
- 1 steel
- 1 steel OR 1 wood
Verdict: POSSIBLE

```

Finally, there may be costs associated with certain production. Here marked as `cost -> production`. Costs are production specific.

```
Requirement: 2 steel
Resources:
- 1 steel
- 1 wood
- 1 wood -> 1 steel OR 0 -> 1 wood
Verdict: POSSIBLE

```

Now, given a set of these resources it is relatively easy to figure out if a given requirement can be fulfilled. What I have currently is a naïve exhaustive search with one optimisation (step 1). In pseudo-python it goes as follows:

```
1. produce with resources that have only one production and no cost to have current "production"
2. can_fulfill(requirement, current production, resource list)

def can_fulfill(requirement, production, resources):
    for i, resource in enumerate(resources):
        remaining = resources[:i] + resources[i + 1:]
        for cost, gain in resource:
            if can_subtract(production, cost):
                new_production = production - cost + gain
                if fulfilled(requirement, production):
                    return True
                recur = can_fulfill(requirement, new_production, remaining)
                if recur:
                    return True
    return False

```

It does work, and for single-production resources it is lightning fast. But in this particular case there can be many resources with multiple production options, which slows the calculation. I think the exhaustive search is my only option, because one can't know which productions ultimately lead to the fulfillment of a requirement, but could there be more clever optimisations I could implement?

My parameters are somewhat conservative for these kinds of optimisation problems I think: I expect to have up to twenty resources, each with up to eight - typically three different productions. In the game there are five production types (steel, wood and 3 more).

# Answer
I suspect this may be NP-hard in general but probably feasible to solve efficiently in practice for the parameter sizes you discussion.

I will suggest an approach based on comments from j\_random\_hacker. One plausible approach is to express this as an integer linear programming problem. Let $a\_{im}$ be the amount of material $j$ you have after the $i$th step of applying sources, $b\_{ir} = 1$ if you apply resource $r$ in the $i$th step or 0 otherwise, and then write constraints to express that each step obeys the rules you've followed. See Express boolean logic operations in zero-one integer linear programming (ILP) for some general techniques for that. For instance, you'll have a requirement that $a\_{im}\ge 0$ for all $i,m$; that $\sum\_i b\_{ir} \le 1$, that $\sum\_r b\_{ir} = 1$; and so on. If you have a resource that contains multiple alternative combinations, treat each as its own resource and then add a constraint that if you pick one of those combinations in any step you can't pick any of the others ($\sum\_i \sum\_{r \in R} b\_{ir} \le 1$, where $R$ is the set of all combinations associated with a single resource). If resource $r$ is "1 wood -\> 1 steel", then we'd obtain a rule like

$$b\_{ir}=1 \implies\\ (a\_{i-1,\text{wood}} \ge 1 \land a\_{i,\text{wood}} = a\_{i-1,\text{wood}} - 1 \land a\_{i,\text{steel}} = a\_{i-1,\text{steel}}+1).$$

Then, convert that to an ILP constraint using the techniques at the link above.

Finally, you can apply an off-the-shelf ILP solver to search for a solution.

Note that the order in which you applies resources matters, because you can never go negative on any material, which complicates the ILP instance a little bit and requires you to have a separate copy of each variable per step.

---

If you prefer to adjust your exhaustive search, there may be ways. One possibility is to use branch-and-bound to prune off some parts of the search space. At any intermediate point in your search, you can get a simple bound on whether it's possible that a solution could exist from here by picking a single material, say wool, counting how many wool you already have, counting how much more wool you could possibly make if you used every remaining wool-producing resource to produce the maximum amount of wool (assuming optimistically all its preconditions can be met), and checking whether that would give you enough wool to meet the target. If not, then there's no point continuing the search from here; you can prune the search. Another way to get a simple bound is to look at the total number of materials, ignoring their type (e.g., total amount of mana, ignoring color); then using each resource that you haven't used so far that increases the number of mana (assuming optimistically that it can be used), and check how much mana total that would give you; if that's not enough for your target, then you can prune the search.

However, ILP solvers already use branch-and-bound, and they are probably doing something that generalizes this and is more powerful. So, rather than implementing branch-and-bound yourself with some limited set of bounds, I suspect it might be more powerful to use a full ILP solver.
> 2 votes

---
Tags: algorithms, optimization
---


# Question
Title: ML Algorithm for getting top pick in each sample
I have a dataset of streets - and each street contains several houses.

```
street_id | house_id | number of calls | number of people living | etc...
1         | 1        | 10              | 5
1         | 2        | 3               | 1
2         | 3        | 4               | 2
2         | 4        | 15              | 19

```
1. My goal is to find for **each street, the most popular house**.
2. I **have GT** \- streets with several houses, and for each street, which house was the most popular house.
3. For the data example above - the results should be *(street 1 -\> house 1, street 2 -\> house 4)* because houses *#1, #4* are the most popular in their street.
4. Popular will be determined with classification algorithm - we have much more features than the 2 above (they are just for example). That's why we have the GT for - so our algorithm can learn what popular is.

We can find the most popular street using features about each house -

* number of calls made from house
* number of people living in house
* etc

But we don't need to find all of the popular houses from all of the houses - **we need for each street, to find the most popular house.**

Do you know how can I solve this task?
I've thought about regular classification, but that would results giving all of the popular houses, and not one for each street.

Thanks in advance!

# Answer
You will have to restructure your data in such a way that one input contains data pertaining to only one street (but of all the houses.) This involves grouping the data by `street_id`.

You should then use several inputs in such a way to train your model to find out the popular house. Since it will be a supervised-learning task, you'll have to label your data accordingly.

But there's a problem here. Each street has different number of houses. One way to handle this problem is by fixing an upper bound on the number of houses per street and padding your data up to this upper bound.
> 1 votes

# Answer
Kedaar, but restructure our data in such a way that one input contains one street, I will classify streets - and not houses. And that's not the goal.
Or you meant each time you classify all of the houses in one street.
> 0 votes

---
Tags: machine-learning, classification
---


# Question
Title: Calculating the Time complexity using Radix sort
Im trying to determine what is the time complexity of sorting numbers with a specific range and base. I have n numbers in the range of 1-n^10 and the base for the radix sort is n/log n. I have tried to calculate it using log equations but im getting to a linear result, I dont know wether im right or wrong. Thank you very much.

# Answer
You are correct. We have $(n/\log n)^{20} \le n^{10}$ for all $n\ge 1$, so each number can be expressed using at most $d=20$ "digits". The running time of radix sort is $O(dn)$, and $O(20n)$ is $O(n)$, so the running time is linear in $n$.
> 1 votes

---
Tags: sorting, radix-sort
---


# Question
Title: Group adjacent sections to create groups with biggest value, value is changing in groups
I have sections 1,2,3...44. We can group only adjacent ones and create groups of maximum size *S* = 4.

There are two possible variations of this problem:

1. can not overlap at all (preferred)
2. can overlap only in outer sections (numbers) /i.e. 1+2+3, 3+4+5+6, 6+7+8 ...

Each section (or group) has it's own value, which is calculated in database query. To simplify, let's assume that it is something like:

```
SELECT COUNT(*) FROM table WHERE section IN (:sectionNumbers)

```

Where sectionNumbers parameter is array of sections in group (1,2,3 i.e.)

The value is **always** greater or equal to value of group with **less elements.** For example group 1+2+3+4 has value of 100 but the same group without element 4 has value of 70(but it could be 100 as well).

Is there an algorithm which can group those sections (numbers) to maximize sum of group values and in same time try to make those groups as small as possible? If there's not such an algorithm, which is the most similar problem to this one? Maybe I can figure out how to solve this with some similar problem solution.

Not every section has to be in group, but if it is possible, merge them.

Correct result for example could be:

```
Group: [1], [2+3+4+5], [5+6+7+8], [9+10+11+12], [13+14+15+16], [16+17+18], [19+20+21] ...
Value: (11)   (965)      (146)       (242)         (600)         (611)       (94)

In this example is section 1 alone, because value of group 2+3+4+5 (965) is higher then if we group 1+2+3+4 (i.e. 300)

```

# Answer
> 0 votes
Your problem can be solved with dynamic programming using a straightforward algorithm. Let $V\[i..i+j\]$ denote the value of a single group with numbers $i,i+1,\dots,i+j$. You say you know all of those values. Let $A\[i\]$ denote the value of the best way to group all of the numbers $1,2,\dots,i$. Then $A\[i\]$ satisfies the recursive equation

$$A\[i\] = \max(A\[i-4\] + V\[i-3..i\], A\[i-3\] + V\[i-2..i\], A\[i-2\] + V\[i-1..i\], A\[i-1\] + V\[i..i\]).$$

Set $A\[-3\]=A\[-2\]=A\[-1\]=A\[0\] = 0$. You can evaluate $A\[1\]$, $A\[2\]$, $A\[3\]$, etc. in that order, using a linear scan. This takes 44 iterations of the loop, and each iteration of the loop uses a few simple lookups and operations, so the total running time will be extremely fast. Finally, $A\[44\]$ holds the solution to your answer, i.e., the value of the best way to group the numbers 1,..,44. If you want to retrieve the grouping itself, you can do that via standard techniques with prev pointers (each time you take a max, remember which one was the largest; or go back and re-compute it).

---
Tags: algorithms
---


# Question
Title: Can I include some manual effort in creating an otherwise automated research prototype tool?
I am a research student in the area of programming language/software engineering. I am claiming to provide an automated technique to solve a research problem in one of my papers. The prototype tool that I am creating for this paper is required to test some real-world libraries. I am using a symbolic execution tool in my research and it crashes on encountering native functions in some third-party libraries. To mitigate this problem, I provide my own model class that is basically a dummy class with non-native functions. Instead of using the original class which contained the native functions, I change the library to use this model class so that symbolic execution works better. Will this be called manual effort in my tool? Can't I call my technique an automated one now? Moreover, is it cheating?

# Answer
> 1 votes
You can do that. I have seen other papers that generate dummy classes like that (e.g., Klee). How useful this will be may depend on how much effort it takes to write those dummy classes and how many are needed.

What matters is less the name (automated vs manual) and more that you describe clearly in your paper what its advantages and drawbacks are. Usually it is valuable to compare to prior papers. Can you demonstrate that your method is easier to apply than prior work? Maybe because it requires less manual work? If so, you may be in business.

---
Tags: research, symbolic-execution
---


# Question
Title: Is the fastest solution for one NP-Complete problem the fastest solution for all NP-complete problems?
This answer seems incorrect to me:

Which NP-Complete problem has the fastest known algorithm?

The fastest solution for one NP-Complete problem should be the fastest solution for all NP-Complete problems.

**Why?**

Can any NP-complete problem be reduced to any other NP-Complete problem in polynomial time?

So, finding some super-optimal exponential time solution, $O(1.27k + nk)$, should be able to be applied to all NP-Complete problems. In other words, the most optimal solution is the same for all NP-Complete problems.

# Answer
A polynomial-time reduction only needs to preserve the size of the problem up to a polynomial upper bound (which is implied by the time constraint).

As an example, suppose you have two NP-complete problems and $A \le\_p B$, the reduction blows up the instance size from $n$ to $n^2$, and $B$ admits an algorithm with running time $ 2^\sqrt{n}$. This only induces an algorithm for $A$ with a running time of $2^{\sqrt{n^2}}=2^n$.
> 5 votes

# Answer
Here is a way to see that there could be arbitrarily large differences between the optimal time complexities of different NP-complete problems.

Suppose P = NP. Then any problem in P with at least one accepting input and at least one rejecting input is NP-complete. By the time hierarchy theorem, there are problems that take $\Theta(n)$, $\Theta(n^2)$, $\Theta(n^3)$, ... time to solve and cannot be solved significantly faster. So if P = NP, then there are NP-complete problems that have asymptotic time complexities of all polynomial exponents (ignoring some log factors in the time hierarchy theorem).
> 2 votes

# Answer
Let's say the NP complete problem A can be solved in O(f(n)), where n is the problem size. And B can be solved in O(g(n)), where g is much larger than f. If we reduce an instance of B to an instance of A, the problem size is very unlikely to stay unchanged. Lets say the problem size is changed from n to h(n), and the time used for the reduction is negligible.

Then solving he instance of B by reducing it to an instance of A will take O (f(h(n))), which may very well be a lot larger than O(g(n)). For example, if both A and B can be solved in O(c^n) for different fixed c \> 1, and the reduction changes the instance size from n to n^2, then the reduction will result in a much slower solution.

So your assumption is completely wrong. 1.27^3 \> 2, so if you have a problem that can be solved in O(2^n), and you use a reduction to your O(1.27^n) problem that increases the instance size just by a factor 3, the reduction leads to a slower algorithm.
> 1 votes

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


# Question
Title: Time complexity of ArrayList Insertion : Calculating sum of X + X/2 + X/4 + X/8 + ... 1
Here is an excerpt from Cracking Coding Interview book where it's talking about the time complexity of insertion to an ArrayList.

I am trying to prove that the sum of $X + \frac{X}{2} + \frac{X}{4} + \frac{X}{8} + .... 1 $ is $2X$.

Given,

\begin{align} & X + \frac{X}{2} + \frac{X}{4} + \frac{X}{8} + .... 1 \\ & = X (1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + .... \frac{1}{X}) \\ & = 2^n (\frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^n}) \\ & = 2^n * S\_{n+1} \end{align}

Here, $S\_{n+1}$ is the sum upto $n+1$ elements,

\begin{align} S\_{n+1} & = \frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^{n-1}} + \frac{1}{2^n} \\ S\_{n+1} - \frac{1}{2^n} & = \frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^{n-1}} \\ S\_{n+1} - \frac{1}{2^n} & = S\_n \end{align}

Also, \begin{align} S\_{n+1} & = \frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^{n-1}} + \frac{1}{2^n} \\ 2S\_{n+1} & = 2 + \frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^{n-1}} \\ 2S\_{n+1} & = 2 + S\_n \\ 2S\_{n+1} -2 & = S\_n \\ \end{align}

Now combining both, \begin{align} S\_{n+1} - \frac{1}{2^n} &= 2S\_{n+1} -2 \\ S\_{n+1} &= 2 - \frac{1}{2^n} \end{align}

As n approaches infinity, $S\_{n+1} = 2$

This is as far as I've gotten. I am wondering how to continue from here. Also, am I in the right path?

---

15 minutes later here is what I've figured out.

Placing the value of $S\_{n+1}$ back to the original expression,

\begin{align} & X + \frac{X}{2} + \frac{X}{4} + \frac{X}{8} + .... 1 \\ & = X (1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + .... \frac{1}{X}) \\ & = 2^n (\frac{1}{2^0} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + .... \frac{1}{2^n}) \\ & = 2^n * S\_{n+1} \\ & = 2^n (2 - \frac{1}{2^n})\\ & = 2^n * 2 - 1\\ & = 2X - 1\\ & \approx 2X \\ \end{align}

But I am not sure if it's correct. I've appreciated some input.

# Answer
Let's take main phrase from your book:

"If you read this sum left to right, it starts with 1 and doubles until it gets to $X$"

This means, that $X=2^k$, for some $k$. So, simply using geometrical progression, we have $$1+2+4+\cdots+2^k=\frac{X}{2^k} +\frac{X}{2^{k-1}} + \cdots+\frac{X}{2^2}+\frac{X}{2}+ X = \frac{1-2^{k+1}}{1-2}=2^{k+1}-1=2X-1$$
> 1 votes

# Answer
The best approach would be to use induction.

Here is a rough outline of a proof I would create:

* X + X/2 + X/4 + X/8 + ... 1 = 2X - 1 is equivalent to 2^k + 2^(k-1) + ... 2^1 + 2^0 = 2\*2^k - 1 for all X=2^k
* Let us create a proposition P(k) which is that: 2^k + 2^(k-1) + ... 2^1 + 2^0 = 2\*2^k - 1
* P(0) is true as 2^0 = 2 * 2^0 - 1
* Let us assume that P(k) is true. P(k+1) is whether 2^(k+1) + 2^k + ... 2^1 + 2^0 = 2\*2^(k+1) - 1
* 2^(k+1) + 2^k + ... 2^1 + 2^0 = 2^(k+1) + 2\*2^k - 1 (Using the fact that P(k) is true)
* 2^(k+1) + 2\*2^k - 1 = 2^(k+1) + 2^(k+1) - 1 = 2\*2^(k+1) - 1
* Hence P(k) implies that P(k+1)
* Hence, by induction P(k) holds for all natural numbers k.
* Hence, X + X/2 + X/4 + X/8 + ... 1 = 2X - 1 ≈ 2X.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Converse proof for random coding capacity of AVC
I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof itself is quite dense (using Lemma 2 in the paper).

I am wondering if there is any work that proves the converse of AVC random coding capacity (shared randomness). If anyone can write the proof here then that works as well. I am ok with a proof for deterministic coding capacity of AVC as well if it is different from the above-mentioned paper.

# Answer
> 2 votes
A complete proof appears in Blackwell, Breiman and Thomasian, The Capacities of Certain Channel Classes Under Random Coding. This paper is linked from the Wikipedia article on AVCs.

---
Tags: proof-techniques, information-theory, coding-theory
---


title: Proving Big-Theta

text:
# Question
Title: Proving Big-Theta
I am having trouble understanding the Big-Theta definition and providing a proof.

Prove that $4n^3 + 3n^2 +2n - 5$ is $\Theta(n^3)$.

I believe using the definition the set up would be as followed:

> Proof: By Big-Theta Definition Let the above expression be denoted as $T(n)$. $T(n)$ is $\Theta(n^3)$ if $c\_1\*n^3 \leq |T(n)| \leq c\_2\*n^3$ for some $n \>= n\_0$.

This part of solving I am having trouble with:

> How do I solve each side to prove that T(n) exists both in $O(n^3)$ and $\Omega(n^3)$?

# Answer
From one hand $$4n^3 + 3n^2 +2n - 5\<4n^3+3n^3 +2n^3=9n^3$$ so for big-$O$ you have $c\_2=9, n\_0=1$.

From another hand $$4n^3 + 3n^2 +2n-5\geqslant 4n^3$$ when $3n^2 +2n-5\geqslant 0$, so for big-$\Omega$ you have $c\_1=4, n\_0=1$.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Are most machine learning problems the same problem? (NP-hard)
I am trying to teach P vs NP to some primarily Machine Learning folks. I wanted to come up with an introductory fact to grab their attention.

**Reasoning for Question:**

> 1. Most problems in Machine Learning are NP-hard.
>
> 2/3. All NP-Hard problems are the same problem - per reduction unto each-other in trivial poly-time.

Thus, it is the case that most Machine Learning problems are actually just the same problem in a different disguises. Is this true?

**Timestamped:** https://youtu.be/YX40hbAHx3s?t=406

An estimate on what percent of Machine Learning algorithms are NP-hard would be helpful. For example, regression is not NP-hard, but I was told that the fact that a closed form solution exists for that particular problem is a *"**miracle**"*. I use the term most loosely. Many will also work.

# Answer
I don't find this a useful or accurate perspective.

It's not true that all NP-hard problems are identical, not even under polynomial-time reductions. All NP-complete problems can be reduced to each other in polynomial time, but NP-complete is different from NP-hard.

When you see someone say something like "all NP-complete problems are the same problem", that is an informal slogan that should not be taken too seriously; you need to look at the technical statement behind that and see whether it is relevant to what you care about. In the context of machine learning, I don't think it's very relevant or useful.

Machine learning is about average-case behavior, not worse-case behavior. NP-hardness is about worst-case behavior.

In machine learning we focus more on behavior on typical problem cases, rather than worst-case problems. For example, the no-free-lunch theorem demonstrates that no ML algorithm will work well on all problems.

In machine learning typically we are more interested in understanding their accuracy rather than their running time, and usually we are concerned with concrete performance on concrete tasks and empirical results rather than asymptotic running time or provable guarantees.

For these reasons, the tools built up for NP-completeness and NP-hardness may not add a lot of insight about machine learning.
> 1 votes

---
Tags: machine-learning, np-hard
---


# Question
Title: What is a Black Box attack against Machine Learning algorithms?
And is there an attack strategy that you can use to approximate the architecture of a machine learning system with the knowledge of class labels and some data points?

# Answer
This is known as a "model extraction attack", and there's a line of research in the computer security literature on this problem. For instance, you might look at the seminal paper by Papernot et al on the subject. A little time on Google Scholar should rapidly turn up dozens of papers on the subject.
> 0 votes

---
Tags: machine-learning, svm, authentication
---


# Question
Title: maximum spanning tree in a complete graph
Given a complete graph how do I find maximum weight spanning tree.
where $weight(u, v) = \sum\_{i=1}^{k} |w\_{i,u} - w\_{i,v}|$

* assuming $k \lt 7$ and $n \le 500000$.
* $n$ number of nodes
* $weight(u,v)$ means weight from node $u$ to $v$
* $w\_{i, u}$ is given for $i \< k$ for a give node $u$
* $k$ is some constant.

# Answer
The best approach would simply be to negate the weight of all edges, and then run an algorithm such as Prim's or Kruskal's, which work with negative edges.
> 1 votes

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


# Question
Title: Does O(1) communication complexity imply that a language is regular?
Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \\{a,b\\}^\*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication complexity $c(m),$ and we let $L = \\{ij \mid g(i,j) = 1\\}.$

Would it be accurate to say that if $c(m) = O(1),$ then $L$ is regular? I'm not entirely sure that this is the case. I've been trying to think about counterexamples to this statement, but I can't really think of any. I do know that the converse is true, namely that if $L$ is regular, then $c(m) = O(1)$. I've been racking my brain over this in the past few days. Any ideas?

# Answer
> 3 votes
No. Let $L\_0$ be a context-free language, say the language of matched parentheses, $L\_1 = \Sigma^\* \setminus L\_0$, and

$$L = \\{ij \mid b \in \\{0,1\\}, i \in L\_b, j \in L\_b, |i|=|j|\\}.$$

Then $L$ is not regular, but it has communication complexity $O(1)$.

# Answer
> 1 votes
Let $L'$ be an arbitrary language, and consider $$ L = \\{ \Sigma^{|x|} x : x \in L' \\}. $$ Then $L$ has roughly the same complexity as $L'$, but it has communication complexity $1$.

---
Tags: complexity-theory, regular-languages, communication-complexity
---


# Question
Title: What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?
I have seen the formulations

> there is no ϵ\>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time

> a problem requires time $n^{2-o(1)}$

> a problem requires time $\Omega(n^2)$

being used in the context of lower bounds but I am not sure as to whether there are relevant differences between these notations or if they are simply equivalent. Intuitively, it seems to me like at least the first and third one are while the second one excludes running times like $n^3$ that are included in the others. However, I have also encountered situations where the second one has been used in a similar way to the first one (i.e. the definitions of the Orthogonal Vectors Hypothesis here, p. 6 and here, p. 6) which suggests to me that they are also equivalent. So how do these notations relate to each other?

# Answer
> 5 votes
It is conjectured that 3SUM cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon \> 0$; equivalently, it requires time $n^{2-o(1)}$. This is *not* the same as the stronger conjecture that 3SUM requires time $\Omega(n^2)$. Indeed, the latter conjecture (which was the original form of the 3SUM conjecture) is false: Grønlund and Pettie came up with an $O(n^2/(\log n/\log\log n)^{3/2})$ algorithm (there were improvements since).

The statement "problem X requires time $n^{2-o(1)}$" states that there exists a function $f(n) = o(1)$ such that any algorithm for X runs in time at least $n^{2-f(n)}$. In particular, there is no $O(n^{2-\epsilon})$ algorithm, for any $\epsilon \> 0$. The converse should also hold, I believe – could be a fun exercise to show.

# Answer
> 2 votes
1. If Your first statement

> there is no $\varepsilon\>0$ such that a problem can be solved in $O(n^{2−\varepsilon})$ time

we understand as negation of

> $\exists\varepsilon\>0,f \in O(n^{2−\varepsilon})$

Then it will be $\forall\varepsilon\>0,f \notin O(n^{2−\varepsilon})$ which is set $$A=\left\lbrace f:\forall\varepsilon\>0, \forall C\>0,\forall N\in \mathbb{N}, \exists n\>N, f(n) \>C n^{2−\varepsilon}\right\rbrace$$ The set from $3$-d statement, $\Omega(n^2)$, as we know, is: $$B=\Omega(n^2)=\left\lbrace f:\exists C\>0, \exists N\in \mathbb{N}, \forall n\>N, f(n) \geqslant Cn^2 \right\rbrace$$ Now if we consider example $$\phi(n)=\begin{cases} 0, & n=2k-1, k\in \mathbb{N} \\ n^3, & n=2k, k\in \mathbb{N} \end{cases}$$ then $\phi\in A$, but $\phi \notin B$.

2. For your second statement if set $C=n^{2-o(1)}$ can be defined as $$C=\left\lbrace f: \exists \varepsilon(n), \lim\limits\_{n \to \infty} \varepsilon(n)=0, \exists N\in \mathbb{N}, \forall n\>N, f(n)= n^{2-\varepsilon(n)}\right\rbrace $$ then again $\phi \notin C$.

So for equivalence there is need some additional restrictions, for example monotonicity, which forbids examples like brought above or we need some other understandings for sets $A,C$.

# Answer
> 0 votes
Beginner myself, but here is my attempt(in Layman terms).

1 ) there is no $ϵ\>0$ such that a problem can be solved in $O(n^{2−ϵ})$ time

This means that the problem cannot have a worst solution with an order of growth of at most $cn^k$ where $k\in \[0,2)$ and $c$ is some +ve constant.

3 ) a problem requires time $Ω(n^2)$

This means that the best solutions to the problem have an order of growth of at least $cn^2$, $c$ being some +ve constant.

---
Tags: complexity-theory, time-complexity, polynomial-time, lower-bounds
---


# Question
Title: Showing that carbon is not a complexity measure per Blum
In Computational Complexity by Papadimitriou, there is an exercise about Blum's axioms where it asks to prove that several measures for the complexity of a Turing machine satisfy them.

> **7.4.12 Blum complexity.** Time and space are only two examples of "complexity measures" for computations. In general, suppose that we have a function $\Phi$, possibly undefined on many arguments, mapping Turing machine-input pairs to the nonnegative integers. Suppose $\Phi$ is such that the following two axioms hold:

> **Axiom 1:** $\Phi(M, x)$ is defined if and only if $M (x)$ is defined.

> **Axiom 2:** It is decidable, given $M$, $x$, and $k$, whether $\Phi(M, x) = k$.

> Then $\Phi$ is called a complexity measure. This elegant formulation of complexity was developed in

> * M. Blum "A machine-independent theory of the complexity of recursive functions," J.ACM 14, 2, pp. 322–336, 1967.

> (a) Show that space and time are complexity measures. (Notice that in this context we do not maximize space and time over all strings of the same length, but leave the dependence on individual strings.) Repeat for nondeterministic space and time.

> (b) Show that ink (the number of times during a computation that a symbol has to be overwritten by a different symbol) is a complexity measure.

> (c) Show that reversals (the number of times during a computation that the cursor must change direction of motion) is a complexity measure.

> (d) Show that carbon (the number of times during a computation that a symbol has to be overwritten with the same symbol) is not a complexity measure.

I am interested in the answer of (d) which I don't know how to approach.

# Answer
> 1 votes
Papadimitriou is being extremely sloppy here. Let us consider part (b) first. What does Papadimitriou mean by "ink"? Suppose that he really means what he wrote: the number of times during computation that a symbol is overwritten by a different symbol. Consider a Turing machine which repeatedly goes right one step, then left one step, in an infinite loop. Then ink is 0, but the machine never halts, and so Axiom 1 seems to be violated. We conclude therefore that ink (and carbon) should be undefined if the machine doesn't halt.

The more challenging bit is proving Axiom 2. Given $M$, $x$, and $k$, we need to decide whether (1) $M$ halts on $x$ and (2) during this halting computation, a symbol is overwritten with a new symbol exactly $k$ times. It might seem at first that this shouldn't be decidable, since we are in some sense trying to solve the halting problem. However, we are given the crucial advice $k$. Let us see how it helps us. We simulate $M$ on $x$ until it either halts (in which case we declare No) or we have reached ink $k$. In the latter case, it remains to check whether $M$ halts on $x$, given the additional promise that the tape doesn't change any more.

The additional promise allows us to continue the simulation until one of the following happens: (1) carbon increases, (2) computation halts, (3) a configuration repeats, (4) we have determined that the machine is off on a tangent on one of the infinite ends of the tape. I leave further details to you.

A similar trick doesn't work for part (d). Indeed, we can arrange for a Turing machine to *never* overwrite a tape symbol with itself. The idea is that for each original tape symbol we will have two new ones, treated in exactly the same way, that are alternated if needed to insure that carbon is zero. It follows that the halting problem can be reduced to the problem of deciding whether carbon is zero or not.

---
Tags: complexity-theory
---