# Question
Title: weighted-clique to vertex cover reduction
> **WEIGHTED-CLIQUE**
>
> * **input:** a undirected graph G that has weighted edges and 2 natural numbers a, b
> * **question:** does G have a clique of size a with total weight of b?

I want to prove that this is NP-hard (assuming weighted-clique $\in NP$)

So I would have to prove

**$VertexCover \leq\_P WeightedClique$**

Need to show the transformation: $(G, k) \to (G', k', d)$

Which ill do by using the fact that $C$ is a vertex cover in $G = (V, E)$ whenever $\bar{C}$ is a clique in $G = (V, E)$ so $\overline{C} = |V| - C$

Hence we can let $G' = \overline{G}$ and $k' = |V| - k$.

I will draw example graphs to illustrate this:

I put 1's in $G'$ just to show that they're weighted as of right now, they have no purpose since I'm not sure how to integrate them into this problem yet.

So ultimately to prove this I need to show

> * If there is a solution to $VERTEXCOVER(G, k)$, then there must be a solution to WEIGHTEDCLIQUE$(\overline{G}, |V | − k, d)$ (1)
> * if there is a solution to WEIGHTEDCLIQUE$(\overline{G}, |V | − k, d)$, then there must be a solution to VERTEXCOVER$(G, k)$ (2)

I only know how to do the (2) part since the $d$ number could just be ignored.

(2) Using the fact from above where $C$ is a vertex cover we know that

If $\forall u, v \in V$, if $u, v \in C$, then $(u, v) \in E$

Taking the contrapositive

$\Leftrightarrow \forall u,v \in V$, if $(u, v) \in \overline{E}$, then $(u \in \overline{C} \text{ or } v \in \overline{C})$. Which makes it clear that $\overline{C}$ is a clique. This is also done in polynomial time since we are going over all pairs of vertices in the original graph which is done in polynomial time.

Now for (1) I'm not sure how to use the vertex cover and get some d such that it holds, if even possible.

Any help appreciated

**edit: did wrong side by accident, fixed it**

# Answer
> 0 votes
Let $G=(V,E)$ be an unweighted graph (think of all the edges as having weight $1$), $n=|V|$, and $\bar{G}$ be the edge-complement of $G$.

Now, $C$ is a vertex cover of $G$ iff $\bar{C} = V \setminus C$ is an independent set of $G$, that is, iff $\bar{C}$ is a clique of $\bar{G}$.

When you combine this with the fact that a clique of size $k$ has $\binom{k}{2} = \frac{k^2-k}{2}$ edges you get: "There is a vertex cover of size $k$ in $G$ iff $\bar{G}$ contains a clique of size $a = n-k$ and weight $b = \binom{n-k}{2}$."

In fact, as far as this reduction is concerned, you can drop either the size or the weight constraint from your clique problem since one implies the other.

---
Tags: np-hard, polynomial-time-reductions
---


# Question
Title: Conjunctive normal form to simple elementary algebra
I'm curious to know the computational complexity class of each step in this method of converting a CNF formula into simple elementary algebra.

An example: $$\phi=\left(x\_1 \vee x\_2 \right) \wedge \left(\neg x\_1 \vee x\_3 \right) \wedge \left(\neg x\_2 \vee \neg x\_3 \right) \tag{CNF} $$ Let $\neg a = 1-a$

Let $a \vee b= a+b-ab$

Let $a \wedge b = ab$

Then: $$\phi=\left(x\_1 + x\_2 -x\_1x\_2\right) \left(1-x\_1+x\_1x\_3\right) \left(1-x\_2x\_3 \right) \tag{AFF} $$ I refer to this step as algebraic factor form (AFF) (I am unfamiliar with any canonical terminology) Then expanding these brackets out gives $$\phi = x\_1-{x\_1}^2+x\_2 - 2x\_1 x\_2 +{x\_1}^2x\_2 + {x\_1}^2x\_3-{x\_2}^2x\_3+2x\_1{x\_2}^2x\_3-x\_1^2x\_2^2x\_3-x\_1^2x\_2x\_3^2-x\_1x\_2^2x\_3^2 + x\_1^2x\_2^2x\_3^2 \tag{EAF}$$ Which is in elementary algebra form.

Finally, using ${x\_1}^2=x\_1, \\; \\; {x\_2}^2=x\_2, \\; \\; {x\_3}^2=x\_3$ we get $$\phi = x\_1-{x\_1}+x\_2 - 2x\_1 x\_2 +{x\_1}x\_2 + {x\_1}x\_3-{x\_2}x\_3+2x\_1{x\_2}x\_3-x\_1x\_2x\_3-x\_1x\_2x\_3-x\_1x\_2x\_3 + x\_1x\_2x\_3$$ Which simplifies to: $$\phi = x\_2 - x\_1x\_2 + x\_1x\_3 - x\_2x\_3 \tag{SEAF}$$ Which I call simple elementary algebra form.

If there are already established names for these formulas please let me know and I will amend asap.

So my question is: What are the computational complexity classes of each transformation in **(CNF)** $\rightarrow$ **(AFF)** $\rightarrow$ **(EAF)** $\rightarrow$ **(SEAF)**

I'm interested to know which parts are P and which parts are NP

Thanks in advance for any answers, Ben

# Answer
$\mathsf{P}$ and $\mathsf{NP}$ are classes of *decision problems*. Essentially, a decision problem is a function $D \subseteq \\{0,1\\}^\ast \times \\{ 0,1 \\}$ (although describing $D$ simply by giving the subset $\\{ 0,1 \\}^\ast \times \\{ 1 \\}$ is more common). A Turing machine is said to solve $D$ if, given any string $x \in \\{ 0,1 \\}^\ast$, it produces $D(x)$. If there is a Turing machine which does so in time bounded by a polynomial $p(|x|)$, then $D \in \mathsf{P}$. If there is a *nondeterminstic* Turing machine capable of doing so in polynomial time, then $D \in \mathsf{NP}$. As you can see, $\mathsf{P}$ and $\mathsf{NP}$ are unrelated to transforming representations of objects into other (equivalent) representations; they are only about saying, for some string $x$, whether $D(x) = 1$ or not.

In your case, what we can do is analyze the time complexity of each transformation. The step CNF $\to$ AFF simply causes the formula to be longer by a constant factor and can be realized in linear time. In AFF $\to$ EAF, the formula blows up exponentially; assuming we previously had a maximum of $t$ terms for each of the $c$ clauses, you go over every possible $t^c$ multiplication of said terms, which takes potentially exponential time. The final EAF $\to$ SEAF step aggregates some terms and may be computed, for instance, in quadratic time (e.g., by looping over each term in the formula). Note that these time complexities are all relative to the respective input length for each step; for instance, "linear" is supposed to mean bounded by $c |\varphi|$, where $\varphi$ is the respective formula which is given as input to the respective transformation step.

I am not aware of a name for the forms you have given. Nevertheless, considering a Boolean formula $\varphi$ as an arithmetic expression (in particular over larger fields) is usually referred to as an *arithmetization* of $\varphi$ and is very relevant in complexity theory; see, for instance, this and this.
> 1 votes

---
Tags: complexity-theory, logic, boolean-algebra, propositional-logic
---


title: Computing an Expression

text:
# Question
Title: Computing an Expression
I am writing code to evaluate the following expression: $$ \frac{(a+b+c)!}{a! b! c!} $$ where $a$, $b$ and $c$ are on the range of $10$ to $500$. The result is going to be a floating point number. I could use a big number package, but the code will run slowly. I am using 64-bit floating point numbers.

I claim by doing as much of the computation in integer (maybe 64 bit) I will minimize the floating point round off error. Therefore, I claim that if put the integers to be multiplied together in an array, cancel common denominators, and then do the final computation in floating point I will minimize round off error.

Do I have this right?

# Answer
You don't need to use integers for any data. Just find the largest of three numbers `x=max(a,b,c)` and reduce both parts by `x!`. Then compute in doubles. For numbers as small as 500 both 32-bit ints and 32/64 bit doubles will be precise.

EDIT: Since 64-bit FP isn't enough to deal with `1500!`, you can perform computations on (decimal) logarithms of multipliers.
> 0 votes

---
Tags: floating-point, numerical-algorithms, numerical-analysis
---


title: Generate random matrix and its inverse

text:
# Question
Title: Generate random matrix and its inverse
I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other. In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that $AB=BA=\text{Id}$.

Is there an efficient way to do this? Can we do it with expected running time approaching $O(n^2)$?

Assume we are working with $n\times n$ boolean matrices (all entries 0 or 1, arithmetic done modulo 2). I am fine with an approximate algorithm (say, it samples from a distribution exponentially close to the desired distribution). My motivation is solely curiousity; I have no practical application in mind.

---

The obvious approach is to generate a random invertible matrix $A$, compute its inverse, and set $A=B^{-1}$. This has running time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant -- something in the vicinity of $O(n^3)$ in practice. Can we do better?

An approach that occurred to me is to choose a set $T$ of simple linear transformations on matrices such that, for each $t \in T$, we can apply the modifications $M \mapsto tM$ and $M \mapsto Mt^{-1}$ in $O(1)$ time. Then, we could set $A\_0=B\_0=\text{Id}$, and in step $i$, sample a random $t$ from $T$, set $A\_{i+1}=tA\_i$ and $B\_{i+1}=B\_it^{-1}$, and repeat for some number of steps (say $O(n^2 \log n)$ iterations). However I'm not sure how we would prove how quickly this approaches the desired distribution.

# Answer
*Efficient Generation of Random Nonsingular Matrices* by Dana Randall covers exactly this topic. In particular **Corollary 1.1** states:

> We can uniformly generate a matrix and its inverse in time $2M(n) + \mathbb{E}\[O(n^2)\]$.

Where $M(n)$ is the time it takes to multiply two $n \times n$ matrices.

Unfortunately this is not better than what you had hoped for.
> 3 votes

---
Tags: randomized-algorithms, matrices, boolean-algebra, sampling, random-walks
---


# Question
Title: Is order of matrix multiplication affecting numerical accuracy of the result?
I have to multiply three matrices of floats: `A` (100x8000), `B` (8000x27) and `C` (27x1).

Is there any difference in accuracy between `A(BC)` and `(AB)C`? If yes - how may I determine the more accurate multiplication order? Speed is not a factor here.

Matrices `A` and `B` contain 8000 samples of (respectively) 100 and 27 features.

# Answer
Yes, there are differences in accuracy since with machine numbers the usual properties of arithmetics don't hold.

Machine numbers are defined as $$ F(\beta,t,m,M)= \\{ 0 \\} \cup \\{ x \in \mathbb{R} : x = sign(x)\beta^{p} \sum\_{i=1}^{t}d\_i\beta^{-i},\ 0 \leq d\_i \lt \beta\ ,\ d\_1\ne 0\ , -m \le p \le M \\} $$ and represent the subset of $\mathbb{R}$ that your machine is able to represent.

All other numbers must be approximated with a number in this subset (usually by truncating the numbers or rounding them).

Let's assume we are in $F(10,2,m,M)$ meaning we are working in base 10 with two digits.

Let $x=0.11\*10^1$, $y=0.31\*10^{1}$ and $z=0.25\*10^{1}$.

The associative property of multiplication doesn't hold:

$(x\*y)\*z = 0.34\*10^1 * z = 0.85\*10^1$

and

$x\*(y\*z) = x * (0.78 * 10^1) = 0.86\*10^1$

other properties that don't hold are:

* the associative property of the addition
* distributive properties
* $x(y/x)$ isn't always equals to $x$
* if $xy=yz$ then isn't always true that $x=z$
> 2 votes

# Answer
At the moment the best solution I have (for a particular set of matrices) is to perform the following numerical experiment:

1. Calculate a reference matrix as an average of products calculated with high precision (e.g. \`np.float128).
2. Calculate test products with lower precision (`np.float64`, `np.float32`, even `np.float16`),
3. Analyse errors calculated as a difference between test products and the reference matrix. The errors are expected to decline as the precision is higher.
> 0 votes

# Answer
Interesting problem. Obviously with floating point involved, you can’t expect the same results, but we’d like to know what tended to give better results?

In a completely unscientific way, you can perform both methods with extended precision and double precision and compare the results. You’d hope that the extended precision results are much closer together, and would guess that the double precision result closer to both is the better one.

If the numbers are small, you could round each to a multiple of 0.1, calculate the product, and since each item in the result must be a multiple of 0.001 you might be able to figure out the exact rounding error.
> 0 votes

# Answer
> how may I determine the more accurate multiplication order?

This is a bit of a frame challenge. To determine the more accurate order you can perform both orders with interval arithmetic. But having done that, you can intersect the intervals to get a more precise answer than either individual order.

Of course, the dot product used will probably be a more important factor than the order of multiplication.
> 0 votes

---
Tags: matrices, numerical-algorithms, numerical-analysis, multiplication, error-estimation
---


# Question
Title: Number of Solutions for Brute Force Algorithm of Travelling Salesperson Problem
We are learning about the travelling salesperson problem in my high school class and we are discussing how computers could solve for the problem, even though the problem is intractable, using a brute force algorithm.
I was wondering if the brute force algorithm calculates ALL possibilities for a number, n, or only UNIQUE possibilities.
For example:
If there were 4 locations, labelled A, B, C & D. Starting from A, would you include both A,B,C,D and A,D,C,B even though they are essentially the same?

Thank you for the help :)

# Answer
> 0 votes
In the classic variant of the Travelling Salesperson Problem, the distance from X to Y is the same as the distance from Y to X for any two locations X and Y. Hence, as you noticed, an algorithm does not *need* to distinguish between the two solutions A, B, C, D and A, D, C, B. However, whether a brute force algorithm considers both solutions or not would depend on how exactly it is implemented. Some will and some won't. It is not too much of a waste to consider them both -- after all, it only takes twice the time. And it may be easier to program the algorithm that way.

There is also a so-called *asymmetric* variant of the Travelling Salesperson Problem where the cost of moving from X to Y is not necessarily the same as the cost of moving from Y to X. Note that in this case, the two solutions A, B, C, D and A, D, C, B are not "essentially the same" anymore and it is important to consider them both.

---
Tags: algorithms, traveling-salesman
---


# Question
Title: Hamming code distance and error detection
Suppose that data are transmitted in blocks of sizes 1000 bits. What is the maximum error rate under which error detection and retransmission mechanism (1 parity bit per block) is better than using Hamming code? Assume that bit errors are independent of one another and no bit error occurs during retransmission.

This is one of the questions from Tanenbaum book.

My approach is since there are 1000 data bits so, 2^r \> = r+data bits +1

r = 10 and so the number of check bits is 10. So, the length of hamming code is 1010. Till here I am able to solve. But how will I get the error rate for the retransmission error detection technique compared to hamming code.

Can anyone explain how to proceed further ?

# Answer
Let's see. With parity, each block is 1001 bits long vs 1010 bit for Hamming code. So if the error rate is 0, then you economize 9 bits.

OTOH, if each second block fails, the in 50% of cases you will have to transmit a second block, in 25% of cases third block and so on. On average you have to send 2 blocks.

Now, let's go deeper. If the error rate is r, this means that each bit fails with the r probability. So, you can compute probability that there are k errors in the block.

You know that if there are 0 errors, you don't need to retransmit block, for a single error you need to retransmit parity-protected block, and for 2n errors you will got unrecoverable error.

Similarly, you can compute it for Hamming code protected block.
> 1 votes

---
Tags: computer-networks, error-correcting-codes, digital-circuits, hamming-code, hamming-distance
---


# Question
Title: Is there a fundamental difference in LIFO and FIFO entropy coding?
The top two competing entropy coders at the moment are Arithmetic Coding (AC) and Asymmetrical Number Systems (ANS).

A very interesting difference between the two is that AC is FIFO and ANS is LIFO. That is, in AC the first symbol you encode into the bitstream is also the first symbol you decode. However with ANS the last symbol you encode is the first symbol you decode.

Is there a fundamental difference between these approaches? Could one be converted into the other? What are the advantages/disadvantages of the two approaches?

# Answer
# LIFO and FIFO encoders with adaptive models are equally capable, with minor implementation differences.

Fabian Giesen writes about this in a blog post:

> ## Reverse encoding
>
> As mentioned above, ANS coders are LIFO: whatever order you encode symbols in, the decoder will produce them in the opposite order. All my ANS coders (including the public ryg\_rans) use the convention that the encoder processes the data in reverse (working from the end towards the beginning), whereas the decoder works forwards (beginning towards end).
>
> With a static model, this is odd, but not especially problematic. With an adaptive model, decoder and model have to process data in the same direction, since the decoder updates the model as it goes along and needs current model probabilities to even know what to read next. So the decoder and the model want to process data in the same direction (forward being the natural choice), and the rANS encoder needs to be processing symbols in the opposite order.

To reiterate, in a FIFO coder,

* Run the model forwards on the data to obtain intervals corresponding to estimated probabilities
* Run the encoder forwards on this list of intervals.
* Run the decoder, generating the decompressed data in its original order.

In a LIFO coder:

* Run the model forwards on the data to obtain intervals
* Run the encoder in reverse on this list of intervals. Streaming is done by encoding in blocks, which can be as large as your memory capacity.
* Run the decoder, generating the decompressed data in its original order.
> 1 votes

---
Tags: coding-theory, entropy
---


# Question
Title: Kleene Star regex question, sed behavior?
Kleene Star with 'sed' is behaving as expected for me, with exception of a case where the input pattern is "ab" and the regex is "b\*". Does anyone know why this regex is not being matched against the pattern space?

This is the failure case:

```
$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000   a   b  \n
0000003

```

**SOLUTION** 'b\*' expects 0 or more occurrences of 'b'. If 0 occurrences of 'b' the empty string $\epsilon$ is expected. In the string above, 'ab' is preceded by the empty string and it is matched in the beginning of "ab" pattern space as follows:

```
printf "ab\n" | sed -En 's/b*/x/ p' | od -t c
0000000   x   a   b  \n

```

where 'x' is substituted for empty string.

In order to match b, I had to use the following form:

Kleene Plus in addition to Kleene Star as follows:

```
 printf "ab\n" | sed -En 's/(.*)(b+)(.*)/\1/ p' | od -t a
0000000   a  nl

```

---

This case, without Kleene Star, behaves as expected:

```
$ printf "ab\n" | sed -En 's/b// p' | od -t c
0000000   a  \n
0000002

```

I'm trying to match the 'b' and replace it with nothing.

The pattern space is 'ab', beginning of line is unspecified, so I'm confused why /b\*/ would not match a pattern of zero or more 'b's, in this case 'b'.

Oddly, this case works with the '.' prepended to the '\*':

```
# fails to match
$ printf "abb\n" | sed -En 's/b*// p' | od -t c
0000000   a   b   b  \n
0000004
# matches with .* !
$ printf "abb\n" | sed -En 's/b.*// p' | od -t c
0000000   a  \n
0000002

```

Kleene Star matches zero or more occurrences of the preceding alphabet (in this case a single character).

By definition:

$V^0 = \\{\epsilon\\}$

$V^1 = V$

$\forall i ( (i \gt 0) \land (V^{i + 1} = \\{ wv : w \in V^i \land v \in V )\\} $

Therefore $V^0 = \\{ \epsilon\\}$, $V^1 = \\{ \epsilon \cdot b\\}$, $V^2 = \\{ \epsilon \cdot b \cdot b\\}$.

$V^\* = \bigcup\limits\_{i\ge0} V^i = V^0 \cup V^1 \cup ...$ which I have specified by `/b*/`.

The following cases agree with my understanding of sed and Kleene Star:

```
# * : matches 0 or more occurances
# no match
$ printf "a\n" | sed -En 's/b*// p' | od -t c
0000000   a  \n
0000002

# match a
printf "a\n" | sed -En 's/a*// p' | od -t c
0000000  \n
0000001

# match a
printf "ab\n" | sed -En 's/a*// p' | od -t c
0000000   b  \n
0000002

# match aa
printf "aab\n" | sed -En 's/a*// p' | od -t c
0000000   b  \n
0000002

```

I tested using BSD and GNU sed, both have the same results.

Thanks!

# Answer
```
$ printf "ab\n" | sed -En 's/b*// p' | od -t c
0000000   a   b  \n
0000003

```

This regex expression "$b\*$" does match the empty string, which is zero '$b$', at the very front of the input "$ab$". This is in accordance with the definition of Kleene star since $b^\*$ stands for the language $\\{\epsilon, b, bb, \cdots\\}$, where $\epsilon$ stands for the empty string. The matched part, an empty substring is replaced by the empty string. So, the same input string "$ab$" is printed with the newline attached.

Note that sed tries to find a match as early as possible. Although the substring "$b$" of "$ab$" matches "$b\*$" more, it is ignored by sed completely since it happens later than the match said above.
> 1 votes

---
Tags: regular-expressions, kleene-star
---


# Question
Title: To check whether the problem of a particular string being a member of CFG G is decidable or not, why can't we use a PDA?
Why can't a TM simulate a PDA? Then we can easily construct a PDA P which is made from grammar G. And contruct a TM that simulates P to prove that this problem is decidable.

# Answer
> 2 votes
Consider a pushdown automaton which has an $\epsilon$-transition which adds $A$ to the stack, and another $\epsilon$-transition that removes $A$ from the stack. Clearly, this PDA has accepting computations of unbounded length. There is no a priori bound on the shortest computation needed to accept a string of a certain length (though perhaps you can come up with such a bound if you're smart enough!).

Why is this a problem? Consider a deterministic Turing machine which runs all possible computations of the PDA, accepting if it finds an accepting computation, and rejecting otherwise. If there is no computable upper bound on the length of a computation, then the Turing machine will have to try infinitely many computations in the rejecting case, and so won't halt on rejecting inputs.

The same problem occurs with context-free grammars having unit productions (consider for example a grammar with the productions $A\to B$ and $B\to A$). After removing unit productions and $\epsilon$-productions, the problem goes away, and you can use dynamic programming to decide the language of the context-free grammar. This is (essentially) the CYK algorithm.

---
Tags: undecidability
---


# Question
Title: Pumping Lemma for Regular Languages with 3 variables (a^nb^mc^m)
I've been trying to understand the pumping lemma, and how to apply it to a language such as a^nb^mc^m where n \>= 0 and m \>= 0. The pumping lemma states that:

For any regular language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and

(1) |uv| ≤ n

(2) |v| ≥ 1

(3) for all i ≥ 0: uviw ∈ L

It states that there exists some n such that this holds true. In the language a^nb^mc^m if I were to replace m with the pumping length, and choose a pumping length, for example 3, such that a^nb^pc^p I could get the string:

aabbbccc

If I chose:

x = aa

y = b

z = bbccc

then xy or aab \<= p and y \> 0. Then if I pump up y by 2 for example, I would get the string aabbbbccc. But this is not in the language as there are more b's then c's. The problem i'm having is if I instead split my string as such:

x = a

y = a

z = bbbccc

then xy or aa \<= p and y \> 0. If I pump this string by 2 for example, I would get the string aaabbbccc, which is in the language. So in this case the pumping lemma is passed.

So my question is, for the pumping lemma does my second example passing mean that the language a^nb^mc^m passes the pumping lemma, or does the fact that I found a case where splitting x and y with this pumping length makes it false, mean that the language does not pass the pumping lemma. And if that is the case then if I had the language:

a^nb^m where n \>=0 and m \>=0 and I choose m to be p, and made the pumping length 3 for example, I could end up with the string:

aabbb, where x = a, y = ab, z = bb, which when pumped would produce aababbb which is not in the language, but I know that a^nb^m is a regular language.

Hopefully you can see where my confusion lies. I been researching for a while and I just can't find a clear cut answer on this. Any help would be extremely appreciated.

Thank you.

# Answer
Apply the pumping lemma on the word $b^nc^n$.
> 1 votes

---
Tags: automata, pumping-lemma
---


title: Calculating LL(1) grammar

text:
# Question
Title: Calculating LL(1) grammar
I am trying to calculate the First and Follow of the following grammar

```
S->ABC
A->Aa
A->aB
B->Bb
B-> epsilon
C-> Cc
C-> Epsilon

```

I have calculated the firsts and it is all good

```
Follow(A) = {a,b,c,$}

```

What is confusing me is the follow of B, I get `Follow(B) = Follow(A)` But on the other hand, I have a solution for the grammar that states that the `follow(B) = {b,c,$}`

So which one is the right one?

# Answer
> 1 votes
It is evident that $B$ can be followed by $a$ — in other words, that $a\in \text{FOLLOW}(B)$ — as shown by the partial derivation

$$\begin{align}S&\to A B C&(S\to ABC)\\ &\to AaBC &(A\to Aa)\\\&\to aBaBC&(A\to aB) \\ \end{align}$$

So the answer provided does not correspond to this grammar.

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Travelling Salesman: Big O Complexity when starting city is fixed
We are studying the Travelling Salesman problem in my high school class, and I am wondering what the Big O complexity of the TSP is when you MUST start and end at the same city. For example, given 4 cities labelled A,B,C,D and you MUST start and end at A, what is the big O notation for this? Is ((n-1)!)/2 for both symmetrical and asymmetric cases?

Thanks

# Answer
> 1 votes
The start city makes no difference. You're constructing a tour through all the cities, so it doesn't matter if you do ABCDEA or CDEABC.

Held–Karp solves TSP in time $O(n^22^n)$, which is much faster than $\Theta(n!)$.

---
Tags: complexity-theory, traveling-salesman
---


title: Doubt on Token in Compiler Design

text:
# Question
Title: Doubt on Token in Compiler Design
Say i have code snippet like --\>

m -= n;

is **minus** and **assignment** considered as a single token or they will be considered as different token?

So the total token count will be 4 or 5?

# Answer
> 1 votes
In the C language you cant insert space between '-' and '=', so you are better to implement '-=' as the single lexeme.

# Answer
> 0 votes
This has mostly to do with programming language design, not compiler design.

As an example, the C language defines that “-=“ is a valid token, and it also says that always the longest possible sequence of characters is used, so in the C language we gave a “-=“ token and not a “-“ token followed by a “=“ token.

The compiler is free to do what it likes but must of course translate the language correctly, so 99.99999999% chances that it creates a single token.

There’s an interesting situation in C++ where \<\< can be used for nested templates. Not sure how the tokeniser would handle it, but the compiler must follow the language rules.

---
Tags: compilers
---


# Question
Title: What is the best way to avoid using goto statements in the pesudocode for an algorithm?
What is the best way to avoid using goto statements when writing the pseudocode for an algorithm?

I want to avoid it and use another way to replace it.

# Answer
> 3 votes
In many cases, GOTO statement can be replaced by loops. For example, in your case, the inner loop is just "while string(i) = path(j), decrease both i and j", and the outer loop is a "loop forever", also known by the C idiom "while true".

# Answer
> 0 votes
Whoever wrote that pseudo code decided to do flow control in the simplest possible way: Using labels and "goto". You'd have to use a different model for pseudocode, for example one which uses loops and "break" statements. Now you made your pseudocode "language" more complicated.

---
Tags: algorithms
---


title: SImple NP-hard proof question

text:
# Question
Title: SImple NP-hard proof question
> $3SATplus$
>
> * Input: 2 CNF formulas $F\_1$, $F\_2$ where all clauses have exactly $3$ literals.
> * Question: Does every truth assignment satisfy at-least as many $F\_2$ clauses as $F\_1$'s?

Assume $3SATPLUS \in NP$

Prove $3SAT \leq\_p$ $3SATplus$

The reduction is as follows

$F\_1 = (x \lor \bar{x} \lor x) \land \dots \land (x \lor \bar{x} \lor x)$

For $n$ clauses. This means it will always accept $n$ clauses.

$F\_2 = F$

This is polytime because its $2n$ clauses only $n$ more than $F$

if $F \in 3SAT$, then $F\_1 = F\_2$ since they both satisfy $n$ clauses so $F\_1, F\_2 \in 3SATplus$

I'll prove the contrapositive

If $F \notin 3SAT$, then $F\_1$ satisfies $n$ clauses and $F\_2$ can satisfies only up to $n-1$ so $F\_1 \> F\_2$ always. Hence, $F\_1, F\_2 \notin 3SATplus$

Is there anything else left to say or does this confirm its $NP-hard$?

# Answer
> 1 votes
If $F\in 3SAT$ it means that there is *some* assignment that satisfies $n$ clauses. It doesn't mean that *every* assignment satisfies all clauses. This makes the reduction wrong, since there might be an assignment for $F\in 3SAT$ that satisfies fewer than $n$ clauses. The reduction you've proposed would be valid if you started with $Tautology$, but then, that problem isn't known to be $NP$-complete.

Your problem is $coNP$-complete (as the reduction from $Tautology$ shows), so finding a reduction from $3SAT$ would prove $NP\subseteq coNP$.

---
Tags: np-hard
---


# Question
Title: Quadratic equations using 2 different approaches
I am reading Mark Newman's Computational Physics and at chapter 4 page 133 in Exercise 4.2 he asks

a) Write a program that takes as input three numbers, a, b, and c, and prints out the two solutions to the quadratic equation $ax^2 + bx + c = 0$ using the standard formula $x = −b± (b^2 − 4ac)^{1/2}/2a$ . Use your program to compute the solutions of $0.001x^2 + 1000x + 0.001 = 0$.

b) There is another way to write the solutions to a quadratic equation. Multiplying top and bottom of the solution above by $-b∓ (b^2 − 4ac)^{1/2} $, show that the solutions can also be written as $x = 2c/−b∓(b^2 − 4ac)^{1/2}$. Add further lines to your program to print these values in addition to the earlier ones and again use the program to

I tried both ways and a) gives me

`[-9.99989425e-13 -1.00000000e+00]` and

b) `[-1.00000000e-06 -1.00001058e+06]`

how can I understand which one is correct ? Or why is this happening ?

# Answer
> 1 votes
You can understand which, if either, solution is correct by substituting it back into the quadratic and seeing which one works.

As to why you get different answers, it's to do with the accuracy of floating point representations. Roughly speaking, numbers are represented to some number of significant figures and this can cause problems when you add numbers with different orders of magnitude or subtract numbers that are approximately equal. For example, evaluated left-to-right to one significant figure, $0.3+0.3+1 = 0.6+1 = 2$, whereas $1+0.3+0.3=1+0.3=1$.

This is a particular issue in the calculation of $b^2-4ac$ in your example, where $b=1000$ and $a=c=0.001$: the correct answer is $999\\,999.999\\,996$, which is very susceptible to even slight rounding errors. You then have to calculate the square-root of that, which gives a number very close to $1\\,000$, and compute $1\\,000$ minus that number. All of these steps cause problems.

The concepts you need to read up on are loss of significance and numerical stability.

# Answer
> 1 votes
**There seems to be something wrong in the first result** you obtained - your case (a) - irrespective of questions to do with floating-point precision and cancellations.

$$x=\frac{-b-\sqrt{b^2-4ac}}{2a}$$ should not cause any problems at all, since there is no cancellation. This value is very nearly $\frac{-2b}{2a}$. The fact that you did not get `1E+06` or something very near to it means that your programming must have been wrong in this case.

$$x=\frac{-b+\sqrt{b^2-4ac}}{2a}$$ is indeed expected to cause problems because you are calculating $-b+{\rm{almost\ }} b$, which largely cancels out. So you would expect a peculiar answer in this case. I wouldn't be surprised, though, to find that once you corrected whatever the problem was with your first calculation, the second one got a little bit less strange as a consequence.

**Your second result does not have this programming problem**. You have got it right.

---

As for your question \[in the comments\] about what to do in general to get accurate roots, I would suggest taking the non-cancelling variant - thus, $-b-\sqrt{b^2-4ac}$ \- to get one root. You can then use the fact that the product of the roots equals $-\frac{c}{a}$ to get the other root.

You would, however, run into different difficulties if $b^2$ were close enough to $4ac$ to give a lot of cancellation under the square root sign. In that case your best bet would be to substitute $y=x+\frac{b}{2a}$, and solve for $y$, since the roots of the quadratic would be very close to $y=0$.

# Answer
> 0 votes
1. In order to check it, compute roots yourself using pencil and paper
2. Floating-point arithmetic: Accuracy problems

# Answer
> 0 votes
This exercise shows you an extremely important concept: Floating point arithmetic always has rounding errors, but the magnitude of those errors can hugely depend on the exact way you arrange your calculation.

First check that both formulas are mathematically the same (common trick: (a-b) = (a^2-b^2) / (a+b)).

Then note that if you calculate both a and b with a reasonably small error, and they are close together, then a-b has a HUGE relative error. Which can totally destroy your calculations.

And think about the shape of the curve 0.001x^2 + 1000x + 0.001. Its close to 0 when x = 0. For positive x it goes to infinity. But for negative x, it goes negative very very quickly until the term 0.001x^2 becomes as large as 1000x with opposite sign, around x =-1000000.

---
Tags: python
---


# Question
Title: Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G
In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:

> Suppose that a friend tells you that a given graph G is hamiltonian, and then offers to prove it by giving you the vertices in order along the hamiltonian cycle. It would certainly be easy enough to verify the proof: simply verify that the provided cycle is hamiltonian by checking whether it is a permutation of the vertices of $V$ and whether each of the consecutive edges along the cycle actually exists in the graph. You could certainly implement this verification algorithm to run in $O(n^2)$ time, where $n$ is the length of the encoding of $G$.

To me, for each consecutive pair $(u,v)$ of the given cycle, we could verify if it's an edge in $G$. Further we could use some color coding for each vertex to ensure we don't revisit a vertex. By doing so, we could verify if the given cycle is Hamiltonian in $O(E)=O(m^2)$ time where $m$ is the number of vertices in $G$. Further we can see the minimum encoding $n$ of $G$ is $m^2=n$. Thus $O(E)=O(m^2)=O(n)$. Can anyone help me understand, why it is mentioned as $O(n^2)$ instead!

# Answer
The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time *also* runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this?

First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has an encoding of size $V^2$. However, if an adjacency list encoding is used, we would only need an encoding of size $O(E \log V + V)$.

Your algorithm does indeed run in $O(n)$ time for a dense graph (with $\sim V^2$ edges); does it also run in $O(n)$ time if the graph is sparse ($O(V)$ edges)? In that case, the encoding might be shorter (if an adjacency matrix is used). Is your algorithm still $O(n)$ in that case? If it enumerates over all potential edges or creates and adjacency matrix, it would not be.

CLRS wants to avoid peculiarities with having to implement the algorithm in a particular way or having to specify a specific encoding, which is why they state "you could *certainly* implement this algorithm to run in $O(n^2)$ time". The "certainly" means "in any case, you can get $O(n^2)$, but it might be possible to do better". In any case, all they care about is that it is polynomial, which both $O(n)$ and $O(n^2)$ are.
> 3 votes

---
Tags: np-complete, np-hard, np, decision-problem, hamiltonian-circuit
---


title: Dubins TSP NP-hardness proof detail

text:
# Question
Title: Dubins TSP NP-hardness proof detail
In Le Ny *et al.*'s paper **On the Dubins Traveling Salesman Problem** (https://tinyurl.com/y59f7d8x) the authors prove, among other works, that the Dubins Traveling Salesman Problem (DTSP) is NP-hard. I will give here the basics of the proof, after which I will ask my question regarding this proof.

The authors reduce Exact Cover to DTSP, by adapting Papadimitriou's reduction from Exact Cover to Euclidean TSP (ETSP). This is done by first noting how Papadimitriou's proof makes it so Exact Cover has a solution if and only if the optimal ETSP tour has length no more than some $L$. Le Ny *et al.* note however that if Exact Cover admits no solution, then the optimal ETSP tour has length at least $L + \delta$, not just $L$, for some defined $\delta$. Next, they note that the optimal DTSP tour length has the following relation with an optimal ETSP tour length : $DTSP \leq ETSP + Cn$, for some $C$ (proven by Savla *et al.*). Le Ny *et al.* then go on to construct Papadimitriou's ETSP instance from a given Exact Cover instance, in which they then multiply all distances by $2Cn/\delta$. They then prove that Exact Cover has a solution if the optimal DTSP tour has length no more than $2CnL/\delta + Cn$, whereas Exact Cover has no solution if the optimal DTSP tour has length at least $2CnL/\delta + 2Cn$.

My question now is, why is it necessary to multiply all distances by $2Cn/\delta$ ? It would seem to me that not multiplying the distances by anything would still result in Exact Cover having a solution if the optimal DTSP tour has length no more than $L + Cn$, and Exact Cover having no solution if the optimal DTSP tour has length at least $L + \delta + Cn$. What am I missing here?

# Answer
> 1 votes
Not multiplying by $2Cn/\delta$, does not result in

> ... Exact Cover having no solution if the optimal DTSP tour has length at least $L+\delta+Cn$.

It in fact would result in a length at least $L+\delta$. This length is not always greater than $L+ Cn$, hence the need to multiply all distances by $2Cn/\delta$, after which one obtains the authors' result : $2CnL/\delta+2Cn$.

---
Tags: np-hard, correctness-proof, traveling-salesman
---


# Question
Title: Can undecidability theorems be detected by a machine?
**this question was originally written in mathoverflow, but a comment recommended me to rewrite it as a CS question.**

This is not a mathematically formalized question. I'm sorry for that but think it's more like mathematics than philosophy.

When we proved a theorem A which says "B is undecidable", we don't try to prove neither B nor (not B). Can a machine do the same thing? Can it detect "meaning" of a statement, like "something is undecidable"?

Here's a reason why I don't think so.

Suppose a sentence

```
universal_Turing_machine(program, input, output)

```

is true if and only if resulting output of "program" with given "input" is "output". Of course, if the program doesn't halt, it would be false for any "input" and "output".

Now, let x be a Godel number of a sentence. Consider the following sentence:

```
there is no y such that:
y is a Godel number of a string which ends with a sentence encoded as x,
and universal_Turing_machine(program, y, true)

```

If the program acts as a "decision program accepting valid proofs", this sentence obviously means "a sentence encoded as x is not provable". If not, this sentence doesn't mean any undecidability. Hence if a machine can detect undecidability theorems, it has to detect programs which act as "decision programs accepting valid proofs"

But according to Rice's theorem, detecting programs which has a specific property is not possible.

Do you think this "reason" makes sense? Since this is not a pure mathematical question, I hope to listen to your opinions. Thank you.

# Answer
> 1 votes
The question is unclear with respect to how exactly it is supposed to be formalized. But formalized must it be because it is asking about the ability of Turing machines to perform certain tasks. So I am going to go ahead and formalize is as best as I can.

Let ZFC be the first-order theory of Zermelo-Fraenkel set theory. We are going to use it as the meta-theory, which is an overkill as a much weaker theory would do. The important thing is that ZFC is powerful enough to be able to talk about first-order languages.

We fix an acceptable numbering of formulas and proofs using natural numbers. Note that the acceptable encodings are all computably isomorphic and nothing changes if we use a different one. So, given a syntactic object $\phi$ (such as a formula), let $\ulcorner \phi \urcorner$ be its code for the given fixed encoding.

The OP speaks about "decidability theorems" and wonders whether there is a formal way of writing down what they are, so let us deal with this first. It is routine to produce first-order formulas in the language of ZFC that express the following:

* $\mathrm{Signature}(x)$ expresses: $x$ encodes a signature for a first-order language.
* $\mathrm{Theory}(x, y)$ expresses $\mathrm{Signature}(x)$ and $y$ encodes a first-order theory (with a decidable set of axioms) in the language over the signature encoded by $x$
* $\mathrm{Prf}(x,y,z,p)$ expresses the fact that $\mathrm{Theory}(x,y)$ and that $p$ encodes a first-order proof in the theory encoded by $y$ of the statement encoded by $z$.

We now have any number of possibilities to formally define what a "decidability theorem" is, and the OP may entertain themselves by exploring the possibilities. To my mind the foloowing is a reasonable definition:

**Definition:** Let $\mathrm{UndecThm}(x, y, z)$ be the formula which expresses the fact that $\mathrm{Theory}(x, y)$ and that $z$ encodes a formula in the language encoded by $x$ of the form $$\forall p \\,.\\, \lnot \mathrm{Prf}(x, y, \ulcorner \phi \urcorner, p) \land \lnot \mathrm{Prf}(x, y, \ulcorner \lnot\phi \urcorner, p)$$ for some sentence $\phi$ (in the language encoded by $x$).

Note: one might be tempted to say that if $A$ is an "undecidability theorem" and $A \iff B$ then $B$ is an undecidability theorem as well, but this is not the case. Logical equivalence does *not* preserve meaning! For example, $A$ might be a undecidability theorem which is true (or provable, if you care about the difference), therefore equivalent to $2 + 2 = 4$, but nobody would claim that $2 + 2 = 4$ is an undecidability theorem.

We may now observe that $\mathrm{UndecThm}(x, y, z)$ is decidable in $x$, $y$ and $z$, quite obviously, as we only need to check that $x$ correctly encodes a signature, that $y$ correctly encodes a first-order theory, and that $z$ indeed encodes a sentence of the form, as given given in the above definition.

The question was whether "machines can detect undecidability theorems". The answer is positive, since $\mathrm{UndecThm}(x, y, z)$ is decidable. Any number of variations on the theme will have a positive answer as well, because one simply has to check that a given code encodes a certain syntactic form. For example, if you slightly vary your notion of "undecidability theorem" nothing will change.

# Answer
> 1 votes
Humans have found undecidability theorems. There is no reason known why an artificial intelligence cannot be built that matches what humans can do intelligence wise (although what is currently fashionable seems to be just pattern matching on a massive scale, which is not going to get you very far), therefore there is no reason known why an artificial intelligence, that is a machine, cannot find undecidability theorems.

# Answer
> 1 votes
I'm not sure I completely understand what you mean. But it looks like just a common misconception.

When we say X is undecidable, it means it isn't possible to find an algorithm that could always generate the correct output for every valid input. But it's possible for an algorithm to generate the correct output only for some inputs, while giving a third result in case it doesn't know the answer.

Likewise, in Rice's theorem, it isn't possible to find an algorithm that could correctly decide whether a program has a specific property for every program. But it's perfectly possible to find an algorithm that could only decide whether each one in a carefully chosen subset of the programs has a specific property.

There are undecidable problems that we could never prove it's undecidable using a certain axiom set. (Say, accept if either the input program halts on empty input, or ZFC is inconsistent.) We could only know some of the undecidable problems are undecidable. So could an algorithm. An algorithm could not "decide" whether a problem is undecidable, or whether a program accepts iff the input is a valid proof, in the sense that such an algorithm cannot always work for any input problem or program. Neither could us.

---
Tags: turing-machines, logic, first-order-logic
---


# Question
Title: Minimal, "natural" set of operations to manipulate a binary tree
Consider binary trees with some abstract values at the leaves. A tree t2 is said to be "derivable" from a tree t1 iff the set of values in the leaves of t2 is included in the set of values in the leaves of t1. In particular, some values can be removed and some can be duplicated.

I'm looking for a minimal set of somewhat "natural" operations on binary trees that can be composed to transform a tree into any of its derivable trees.

By natural I mean operations which are local to the root of the tree or its vicinity, happen in constant time, and can be somewhat visualized.

For instance, swapping the left and right subtree of the root of performing AVL like rotations would qualify as natural operations.

# Answer
It looks like the following set of four operations is sufficient. They are also minimal / necessary in the sense that no single operation can be removed from the set.

* right rotation at the root:

```
    .            .
   / \          / \
  .  z    =>   x   .
 / \              / \
x   y            y   z

```
* duplicating the tree
* deleting the left branch
* flipping the right grandchildren

By way of illustration (and a form of proof outline), I've written up a Haskell implementation. Given a definition of a `Tree` structure and a `TreeOp` tree operation type:

```
data Tree a = Node (Tree a) (Tree a) | Leaf a
type TreeOp a = Tree a -> Maybe (Tree a)

```

the primitive operations would be defined as:

```
rotateR, dup, deleteL, flipR :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

```

We can define derived operations to flip the root's children (duplicate the tree, flip the right grandchildren, and delete the left branch):

```
flipC :: TreeOp a
flipC = dup >=> flipR >=> deleteL

```

Similarly, we can define an operation to duplicate the right branch:

```
dupR :: TreeOp a
dupR = dup >=> rotateR >=> flipR >=> deleteL >=> rotateR

```

as well as the symmetric variants of all the above operations:

```
flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC >=> flipR >=> flipC
deleteR = flipC >=> deleteL
dupL = flipC >=> dupR >=> flipC
rotateL = flipR >=> flipC >=> rotateR >=> flipR >=> flipC

```

Finally, it will be helpful to have an operation for "interleaving" the grandchildren like so:

```
        ..           ..
       /  \         /  \
      .    .       .    .
     / \  / \     / \  / \
     w x  y z     w y  x z

```

The best implementation I could come up with was:

```
interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  >=> flipL >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL >=> flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  >=> flipR >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR >=> flipR

```

With `interleave`, it's easy to define operations to rotate the left and right subtrees of the root independently:

```
rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR >=> flipL >=> interleave >=> rotateL >=> flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL >=> rotateR >=> interleave >=> flipL >=> rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC >=> rotateLR >=> flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC >=> rotateLL >=> flipC

```

Using a helper to apply an operation repeatedly until it no longer works:

```
untilDone :: (a -> Maybe a) -> a -> a
untilDone op t = maybe t (untilDone op) (op t)

```

we can turn any tree into an in-order traversal "cons-list-like" normal form:

```
toList :: Tree a -> Tree a
toList
  = untilDone rotateR
    >>> untilDone (untilDone rotateRL >>> rotateL)
    >>> untilDone rotateR

```

meaning that, for any tree `t` whose in-order traversal of leaves is, say, `[1,2,3,4,5]`, the result of `toList t` will be:

```
Node (Leaf 1) (Node (Leaf 2) (Node (Leaf 3) (Node (Leaf 4) (Leaf 5))))

```

Now, this normal form is just a zipper under the `rotateL` and `rotateR` operations -- we can `rotateR` it to any point in the list, with the "rest" of the list elements on the right branch in normal form, and the preceding elements on the left branch in an "inverted" normal form (with leaves on the right branches instead of the left).

Applying `interleave` to such a zipper will swap adjacent elements at the zipper's cursor in the general case, though the following function also handles the corner cases where `interleave` fails because the left or right branch is just a leaf:

```
swapLeaves :: TreeOp a
swapLeaves = interleave
  `orTry` (rotateR >=> flipR >=> rotateL)
  `orTry` (rotateL >=> flipL >=> rotateR)

```

Here, `orTry` isn't a separate operation -- it's just a conditional control structure that handles the case where a generalized operation fails because, say, the left branch is only a leaf instead of a larger inverted cons list:

```
orTry :: TreeOp a -> TreeOp a -> TreeOp a
orTry op1 op2 t = op1 t <|> op2 t
infixl 1 `orTry`

```

We can also duplicate the element to the left of the cursor with:

```
dupLeaf :: TreeOp a
dupLeaf = (flipL >=> rotateR >=> dupL >=> rotateL >=> flipL >=> rotateLR)
  `orTry` dupL

```

This doesn't handle two corner cases: we can duplicate the rightmost element (i.e., duplicate an element to the right of the cursor) with a `swapLeaves >=> dupLeaf => swapLeaves => rotateR => swapLeaves` combination, and if the tree is a lone leaf, we can just duplicate it with `dup`.

We can delete the element to the left of the cursor with:

```
deleteLeaf :: TreeOp a
deleteLeaf = (flipL >=> rotateR >=> deleteL) `orTry` deleteL

```

and the last element with a `swapLeaves >=> deleteLeaf` combination\`.

I think it's clear that with there operations to swap, duplicate, and delete leaves together with rotations through the zipper, we can turn any in-order cons list into any other in-order cons list constructed from a subset of its elements.

And, since `toList` uses only reversible operations, it follows that we can reconstruct the final tree from its in-order cons list, so I think that probably completes the proof that these operations are sufficient.

To establish that they're "minimal" / necessary, we need to show that dropping any one of the primitive operations would make it impossible to handle some case. It's easy to see that `dup` and `deleteL` are necessary, as they're the only operations that can add or remove leaves, respectively. With the exception of `rotateL`, all the other operations preserve the binary tree property of "perfection" or "perfect balance" (i.e., the property of having all leaves at the same level), so `rotateR` is necessary to create an unbalanced tree from a perfectly balanced one. And finally, `flipR` is necessary as no remaining operations can change the in-order traversal of a tree's leaves (oops -- actually, this isn't convincing, since `dup` and `deleteL` can do this; I'll need to think about this one).

Anyway, here's the full code to play with:

```
{-# OPTIONS_GHC -Wall #-}
import Data.Maybe (fromJust)
import Control.Monad
import Control.Applicative
import Control.Arrow ((>>>))
data Tree a = Node (Tree a) (Tree a) | Leaf a
data Side = L | R
type TreeOp a = Tree a -> Maybe (Tree a)

rotateR, dup, deleteL, flipR, interleave :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

flipC :: TreeOp a
flipC = dup >=> flipR >=> deleteL

dupR :: TreeOp a
dupR = dup >=> rotateR >=> flipR >=> deleteL >=> rotateR

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC >=> flipR >=> flipC
deleteR = flipC >=> deleteL
dupL = flipC >=> dupR >=> flipC
rotateL = flipR >=> flipC >=> rotateR >=> flipR >=> flipC

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  >=> flipL >=> rotateR >=> flipL >=> rotateR >=> deleteL >=> rotateL >=> flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  >=> flipR >=> rotateL >=> flipR >=> rotateL >=> deleteR >=> rotateR >=> flipR

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR >=> flipL >=> interleave >=> rotateL >=> flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL >=> rotateR >=> interleave >=> flipL >=> rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC >=> rotateLR >=> flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC >=> rotateLL >=> flipC

untilDone :: (a -> Maybe a) -> a -> a
untilDone op t = maybe t (untilDone op) (op t)

toList :: Tree a -> Tree a
toList
  = untilDone rotateR
    >>> untilDone (untilDone rotateRR >>> rotateL)
    >>> untilDone rotateR

swapLeaves :: TreeOp a
swapLeaves = interleave
  `orTry` (rotateR >=> flipR >=> rotateL)
  `orTry` (rotateL >=> flipL >=> rotateR)

orTry :: TreeOp a -> TreeOp a -> TreeOp a
orTry op1 op2 t = op1 t <|> op2 t
infixl 1 `orTry`

dupLeaf :: TreeOp a
dupLeaf = (flipL >=> rotateR >=> dupL >=> rotateL >=> flipL >=> rotateLL)
  `orTry` dupL `orTry` dup

deleteLeaf :: TreeOp a
deleteLeaf = (flipL >=> rotateR >=> deleteL) `orTry` deleteL

pprint :: (Show a) => Tree a -> IO ()
pprint = putStrLn . unlines . pshow
pshow :: (Show a) => Tree a -> [String]
pshow t = case t of
  Leaf x -> [center 5 $ show x]
  Node x y -> bar ++ xy'
    where x' = pshow x
          y' = pshow y
          xy' = hjoin x' y'
          lft = width x' `div` 2
          rgt = width y' `div` 2
          rest = width xy' - lft - rgt
          bar = [ justify lft rgt $  '.' : replicate (rest - 2) '-' ++ "."
                , justify lft rgt $  '|' : spaces (rest - 2) ++ "|" ]
  where
    spaces = (`replicate` ' ')
    justify l r str = spaces l ++ str ++ spaces r
    width = length . head
    center n str = justify l (l+u) str
      where (l, u) = (n - length str) `divMod` 2
    hjoin x y = go x y
      where wx = width x
            wy = width y
            go (l:ls) (r:rs) = (l ++ r) : go ls rs
            go [] rs = map (spaces wx ++) rs
            go ls [] = map (++ spaces wy) ls

t1, t2 :: Tree Int
t1 = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3) (Leaf 4))
t2 = Node t1 (Node (Node (Leaf 5) (Leaf 6)) (Node (Leaf 7) (Leaf 8)))

main :: IO ()
main = do
  pprint t1
  pprint . fromJust $ interleave t1
  pprint . fromJust $ toList >>> rotateR >=> rotateR $ t1

```
> 1 votes

# Answer
I don't have a proof but I would consider these operations:

* tree rotations (as in AVL trees / red-black trees)
* removing a leaf
* duplication: replacing a leaf $x$ by a node having two leaf children $x$
* swapping: if a node has two leaf subtrees, swap them

My conjecture is: using tree rotations you can transform the tree into any other tree which has the same leaves, taken according to the in-order visit. E.g. the tree $(1,(2,3))$ can be rotated into $((1,2),3)$, which has the same in-order visit $1,2,3$.

If that holds, we need swaps (at least on the leaves, if not of general subtrees) so to generate all the possible leaves permutations. Alternatively, we could also take any subset of the permutation group which generates the whole group: one might check out an abstract algebra book to find a few example.

After that, leaf removal and duplication can be added so to get the wanted relation.

Again, this needs to be proved carefully -- the above one is only an intuition.
> 0 votes

---
Tags: binary-trees
---


# Question
Title: Algorithm to compute partitions of a graph in N cliques
does anyone know of an efficient algorithm to compute the partition of a graph in N cliques?

Notice that N is the number of the cliques and not the size of them.

I have heard of the 2 cliques problem, but I'm interested in the more general version.

# Answer
This problem is known as clique cover and it's NP-complete. In other words, no efficient algorithm is known.
> 3 votes

---
Tags: graphs, reference-request, clique
---


# Question
Title: What is the time complexity of LR parsers?
Bottom up parsers in worst case take O($n^3$) time, and i believe that LR parser being a bottom up parser should also take O($n^3$) time, but i read on wiki that they are able to solve problems in linear time. How can this be possible?

# Answer
> 2 votes
It's because they can only recognise a subset of context-free languages. In fact, it is the subset which can be parsed in linear time: languages with a deterministic grammar.

---
Tags: compilers, parsers
---


# Question
Title: Difficulty in proving the existence of one-way functions
By definition:

A polynomial-time computable function $f:$ $\\{$0,1$\\}$$^\*$$\\{$0,1$\\}$$^\*$ is a *one-way function* if for every probabilistic polynomial time Turing Machine $PTM$ there is a neglegibible function $E$ $:$$\mathbb{N} → \mathbb{N} $ $ \ s.t. \ $ $Pr$ $x$ $∈$ $\\{$0,1$\\}$$^n$ $\[PTM \ \ inverts \ \ f(x)\] ≤ E(n)$.

Now, reading the definition above, the existence of one-way functions seems like an easy bet, however it is considered a stronger assumption than $P \neq NP$. Apparently proving the existence of these functions would be more difficult than proving $P = NP ?$ And I'd like to know the technical reasons for this, does it have something to do with the "**for every**" in the definition?

What steps would a mathematician or computer scientist take to prove that *one-way functions* exist? I believe that since proving its existence would also prove $P \neq NP$, this means that we cannot use the techniques that we know for sure does not work: **Relativization**, **diagonalization**, **Natural Proof**.

So, what form could such a proof take? Maybe something in second(+)-order logic?

# Answer
> Apparently proving the existence of these functions would be more difficult than proving $P\not =NP$? And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

The answer is in your question itself:

> I believe that since proving its existence would also prove $P\not =NP$

This is indeed the case. Somebody that proves the existence of one-way functions automatically also proves $P\not = NP$. On the other hand, it is conceivable that you could prove $P\not = NP$ without proving that one way functions exist. Thus, proving the existence of one-way functions is at least as hard as proving $P\not = NP$.

> What steps would a mathematician or computer scientist take to prove that *one-way functions* exist?

Coming up with an extremely clever and creative idea that nobody came up with before.
> 1 votes

---
Tags: one-way-functions
---


# Question
Title: Proving that an $n$-element heap has at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes
I am having trouble proving that an n-element heap can have at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes.

Please note that I am proving a loose bound.

First I proved that a complete binary tree can have at most $2^{h+1} - 1$ nodes. However, I don't know how to use this fact to inductively prove the formula above?

The only thing thus far in my inductive proof is showing the base case ($h=0$), which is trivial.

# Answer
> 5 votes
Probably, you mean this: A heap of size $n$ has at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes with height $h$.

Proof can be found for example here: http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN\_2.pdf

# Answer
> -1 votes
This is the actual question should be (Coreman 6.3-3) :A heap of size n has at most ⌈n/2^(h+1)⌉ nodes with height h.

This is just a simple intution for the proof.

This is an easy to prove property of complete binary tree/heap that is no. of leaf nodes = (total nodes in tree/heap)/2 {nearly}

Now, no. of nodes at height 0 = n/2 (because all leaf nodes are at maximum depth)

So traversing from bottom to top of tree, the height keep on increasing height by one, at each level we have no. of nodes = (no. of nodes from root to that level)/2, and once we finished counting that level we're left with same problem for half of the total node upto this level, for a level above (Think recursively, at each step although increasing the height, but deleting leaf nodes, and redoing the problem with 1/ of the nodes).

Therefore, no. of nodes at : At height 1 = (n/2)/2 = n/4, At height 2 = (n/4)/2 = n/8, . . . At height h = n/2^(h+1) {observing the trend}

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


# Question
Title: If the human brain is a Turing machine then how is it able to ascertain that certain problems are undecidable?
I recently read about the idea that the human brain might be a Turing machine (or Turing complete). If that is true then how is the brain able to reason that a certain problem is undecidable for e.g. the the liar paradox. I assume that a Turing machine will nor be able to reason that the liar paradox statement is a logical paradox with no decidable answer and will be stuck forever.

# Answer
> I assume that a Turing machine will nor be able to reason that the liar paradox statement is a logical paradox with no decidable answer and will be stuck forever.

Why do you assume that? It's perfectly possible for a Turing machine to recognize a specific paradox and to have logic systems that include the concept of paradox.

Also, note that undecidability is a separate concept to paradox. A paradox is a statement that is neither true nor false: it is a property of sentences in formal systems. Undecidability is a property of languages, which are sets of finite strings: specifically the property that there is no Turing machine that correctly determines which strings are in the set and which are not.
> 1 votes

---
Tags: turing-machines, computation-models, turing-completeness, neural-computing
---


title: 3-CNF to "independent form"

text:
# Question
Title: 3-CNF to "independent form"
Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\wedge$). Any combination of operations is allowed, though the fewer operations used the better.

$$ \left((a \rightarrow b ) \downarrow b \right) \wedge \left(c \vee d\right) \wedge \left( \left(e \leftarrow f\right) \vee f \right) \tag{IND} $$

This would be valid because all instances of each variable exist in only 1 of the "factors" even if it appears in that factor multiple times.

$$\left((a \rightarrow b ) \downarrow b \right) \wedge \left(a \vee b\right) $$ This would be invalid because the $a$ (or the $b$) appears in multiple AND "factors"

I have called this **(IND)** because each of the factors is independent of each other. I'm mainly interested in a way to convert 3-CNF to **(IND)**, if it is possible.

---

Edit for clarification:

Consider $\left( a \vee b \vee c\right) \wedge \left(a \vee d \vee e \right)$. The $a$ appears on both sides of the $\wedge$ I would like to convert it into format: $ f(a,b,c) \wedge g(d,e)$ where $f(a,b,c)$ and $g(d,e)$ can use any operations.

Similarly

Given $\left( a \vee b \vee c\right) \wedge \left(a \vee b \vee d \right)$ I would like the $a$ and $b$ to be on the same side of the $\wedge$. It doesn't matter how they are separated, or if any of the other variables move. All that matters is that each instance of a variable appears in only 1 "factor"

$\underbrace{\left( a \vee b \vee c\right)}\_{factor} \wedge \underbrace{\left(d \vee e \vee f \right)}\_{factor} \wedge \underbrace{\left(g \vee h \vee i \right)}\_{factor}$

# Answer
> 2 votes
> Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\land$)

In general, it is impossible to separate variables in that way. Consider the formula $a \leftrightarrow b$, and assume it can be written in the form $f(a) \land g(b)$.

Up to logical equivalence, $f(a)$ must be either $a$ or $\lnot a$. Ditto for $g(b)$. We therefore have that $f(a) \land g(b)$ must be one of these formulas:

$$ a\land b \qquad a\land \lnot b \qquad \lnot a\land b \qquad \lnot a\land \lnot b \qquad $$

However, none of the above ones is equivalent to $a \leftrightarrow b$.

(Well, to be pedantic, $f(a)$ and $g(b)$ could also be the constantly true or constantly false function. Those choices won't work either, obviously.)

---
Tags: logic, boolean-algebra, propositional-logic, 3-sat
---


# Question
Title: Is binomial(n, k)=0 (mod n) when gcd(n, k)=1? When gcd(n, k)>1?
I was programming the AKS primality test, and I have two questions.

Is it correct that if gcd(n, k)=1, then binomial(n, k)=0 (mod n)?

Is it correct that if gcd(n, k)\>1, then binomial(n, k)\>0 (mod n)?

# Answer
All variables are understood to be positive integers. Let $n\mid m$ mean $n$ is a factor of $m$, a.k.a. $m$ is divisible by $n$ or $m=0\pmod n$.

> Is it correct that if $\gcd(n, k)=1$, then $n\mid\binom nk$?

Yes.

Since $k\binom nk=n\binom{n-1}{k-1}$, we know $k\binom nk$ is divisible by $n$. Since $\gcd(n,k)=1$, we must have $\binom nk$ is divisible by $n$.

---

> Is it correct that if $\gcd(n, k)\>1$, then $\binom nk\>0\pmod n$?

The relation of "greater than" or "less than" modulo $n$ does not make sense since, for example, $-1=1=2019\pmod 2$.

What you have in mind should be the following question.

> Is it correct that if $\gcd(n, k)\>1$, then $n\not\mid\binom nk$?

Not necessarily.

The smallest counterexample is $\gcd(10,4)=2\neq1$ but $10\mid\binom{10}4=210$. In fact, if $n=2\pmod8$, then $n\mid\binom n4$.

---

Kummer's theorem provides a way to compute the exponent of the highest power of a given prime number dividing a binomial coefficient. Peter Taylor points out that it can be used to determine whether $n\mid\binom nk$ in polynomial time if we know the prime factorisation of $k$ or $n$. However, no algorithm is known to be able to obtain the prime factorisation of an integer in polynomial-time.

Here is a related interesting article, *divisibility properties of binomial coefficients* by K. R. Mclean.

---

**Exercise 1**. Show that if $m\mid n$ and $\gcd(m,k)=1$, then $m\mid\binom nk$.

**Exercise 2**. Show that $2i\mid\binom{2i}4$ iff $i=1\pmod4$.

**Exercise 3**. Find infinitely many pairs of $n$ and $k$ such that $1\lt k \mid n$ and $n\mid\binom nk$. (Hint, one such family can be found by setting $k=6$.)
> 1 votes

---
Tags: algorithms, primes
---


# Question
Title: Is a "protocol" a set of algorithms and data structures?
I'm not major in science at all and would like to verify whether my understanding is correct or not.

I just did some googling about the definition of protocol, such as in this, this one, this one and more.

And, I would like to know:

1. is a protocol a pack of algorithms and programming source codes? (in both the computer and network)
2. regarding the previous question, if so, does that mean that the operating systems/network nodes/applications/hardware indeed have such packs of codes inside their body to perform communications to each other that follow the same protocols? (such as TCP/IP, smb, secure shell, SMTP...)

# Answer
> is a protocol a pack of algorithms and programming source codes? (in both the computer and network)

No. A protocol is an abstract description of how systems communicate. Source code could be an *implementation* of a protocol, but the protocol is not the same as its implementation. Basically, a protocol tells a programmer "the messages should be formatted like this and you should respond in this way to this message", but it is up to the programmer to decide how to implement this in an algorithm and/or source code.

> regarding the previous question, if so, that means the operating systems/network nodes/applications/hardware indeed have such packs of codes inside their body to perform communications to each other that follows the same protocols? (such as TCP/IP, smb, secure shell, SMTP...)

Yes, operating systems and other hardware do contain code (or sometimes specialized hardware) that implements protocols. However, the way a protocol is implemented may (will) be different between different operating systems and pieces of hardware. The protocol sets standards for how the system should behave to the outside world, but not for how this is implemented internally.
> 3 votes

---
Tags: communication-protocols, protocols
---


title: Path of exact cost k in DAG

text:
# Question
Title: Path of exact cost k in DAG
struggling with this question from an exam:

**input**:

DAG G=(V,E). each edge $e\_i$ has weight $w\_i\in \text{{0,1,2,3}} $

Two vertices : s,t

Number: k

**output**:

`A path from s to t with total cost k (if exists)`

# Answer
> 2 votes
When you get a question about a DAG, the first thing to do is a topological sort.

Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ \+ the weight of $e$.

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


# Question
Title: Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems
I have a method to solve the $\mathsf{\\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an example here.

> How many solutions does $\phi=\left(x\_1 \vee x\_2 \right) \wedge \left(\neg x\_1 \vee x\_3 \right) \wedge \left(\neg x\_2 \vee \neg x\_3 \right)$ have?

First convert to a boolean polynomial: $$\phi=\left(x\_1 + x\_2 -x\_1x\_2\right) \left(1-x\_1+x\_1x\_3\right) \left(1-x\_2x\_3 \right)$$

Expand and simplify (using, e.g., $x^2=x$ for Boolean values): $$\phi = x\_2 - x\_1x\_2 + x\_1x\_3 - x\_2x\_3$$

Substitute $x\_1 = x\_2 = x\_3 = \frac{1}{2}$ and multiply by $2^n$ where $n$ is the number of variables: $$|\phi| = 2^n\left(\frac{1}{2} - \frac{1}{4} + \frac{1}{4} - \frac{1}{4}\right) = 2^3\frac{1}{4} = 2$$

where $|\phi|$ is the number of solutions that $\phi$ has.

And indeed, those 2 solutions are $(0,1,0)$ and $(1,0,1)$.

---

I have proven that this works for any logical expression. Does this have any use/bearing on $\mathsf{\\#P}$ vs $\mathsf{NP}$?

# Answer
> 5 votes
As I have hinted at in the comments, that your reduction exists is not at all surprising. As in my answer to your previous question, your "Expand and simplify" part takes potentially exponential time and, thus, does not qualify as a polynomial-time reduction (which is the standard notion used to compare the classes in question). Exponential-time reductions here are irrelevant because both $\mathsf{NP}$ and $\\#\mathsf{P}$ are contained in $\mathsf{EXP}$, so the reduction is powerful enough to *solve* the problems it should be reducing.

As to address the question in the title, notice the following: Let $P \in \mathsf{NP}$ be some problem, $S\_P$ the solution set associated with $P$ (i.e., the $\\{0,1\\}^\ast \times \\{0,1\\}^\ast$ relation which, for instance, associates each $x \in P$ with its (poly-time verifiable) solutions), and $\\#S\_P\colon \\{0,1\\}^\ast \to \mathbb{N}\_0$ be the counting problem associated with $S\_P$, that is, $\\#S\_P(x) = |S\_P(x)|$. For $P = \mathsf{SAT}$, for example, $S\_P$ is simply the relation of formulas to their satisfiable assignments, and $\\#S\_P$ the number of satisfiable assigments. Then you can recast $P$ as the (decision) problem $\\{ x \mid \\#S\_P(x) \ge 1 \\}$. This means that having a procedure which counts solutions (i.e., computes $\\#S\_P \in \\# \mathsf{P}$) directly yields something which decides $P \in \mathsf{NP}$.

Not only that, but notice that above we do not even actually use the value $\\#S\_P(x)$ other than to test that it is not zero. It is conceivable that we can use that accurate value towards solving problems much harder than $\mathsf{NP}$ (e.g., as Toda's theorem tells us; see David Richerby's answer). This gives us enough reason to believe that problems in $\\#\mathsf{P}$ are, in general, *much* harder than those in $\mathsf{NP}$ (the most conspicuous candidates being the $\\#\mathsf{P}$-complete problems).

# Answer
> 2 votes
By Toda's theorem, there are randomized reductions from every problem in the polynomial hierarchy to any #P-complete problem. As such, an NP algorithm for any #P-complete problem would be a huge deal.

However, your algorithm doesn't actually seem to use any nondeterminism, so either you've proven that P=#P (which implies P=NP along the way) or you've made a mistake somewhere.

---
Tags: complexity-theory, logic, counting, propositional-logic
---


# Question
Title: Is stack based memory allocation memory allocated at run time or compile time?
In stack-based memory allocation: is memory allocated at compile time? If so, then how can we allocate space for, say, n number of recursive calls made during the execution of the program?

# Answer
The amount of stack space allocated to a process (or a thread, if you are talking about multithreading) is decided at run time, when it starts - usually by the system, which just allocates a fixed amount without regard to what the program might actually need: "allocate a megabyte and keep your fingers crossed". Alternatively, when creating a thread within a program, it is sometimes (depending on the system) possible for the programmer to specify the size of the stack required by the thread - but this, too, is done before knowing what the thread's real requirements might be.

With virtual memory, of course, what is really allocated is address space rather than actual memory, so in principle one could just increase the address space allocated to each thread and cross one's fingers a little less. But the same point remains: a fixed limit is being imposed, in advance, without knowing what is actually going to be needed.

Ultimately no reliable computer system can have **both** unlimited recursion **and** stack-based storage. Mainframes such as the IBM 360 did not use stacks for return addresses or for local storage. There are "stackless" implementations of various programming languages - **any** programming language could be implemented stacklessly if people really wanted to do it.

This Stack Exchange answer goes into much greater detail, more rigorously.
> 1 votes

---
Tags: memory-management
---


# Question
Title: Time complexity, Big-O for this function?
```
def f(n):
    if n < 100000:
        return 0;
    for(int i = 0; i < n*n; i++){
        return f(n-1)
    }

```

**What is the time complexity?**

---

My answer is $O((n!)^2)$. Here's my thought process:

1. The for loop will be running $n^2$ the first time.
2. However, during the first loop (i.e., $i = 0$), it will call $f(n-1)$, hence the next for loop will be $(n-1)^2$.
3. This will keep going until $n \<10000$ (base case). Assuming $n$ is very huge, the number of calls for each function to base case is essentially $n$ times.
4. Now, considering all the for loops, the total number of calls is essentially $n^2 \cdot (n-1)^2 \cdot (n-2)^2 \cdots 1!$ (there will be a total of $n$ times multiplication, and each multiplication will be $n-1$ of the previous one because of $f(n-1)$ call).

# Answer
> 4 votes
It runs in time $O(n)$. Remember that a function only `return`s once. In each call to `f`, the `for` loop is immediately terminated at `i=0` by the `return` statement, so the function body is equivalent to

```
if n < 100000
    return 0;
else
    return f(n-1);

```

However, your answer of $O((n!)^2)$ is not wrong: $(n!)^2$ is a huge overestimate of the running time, but big-$O$ essentially means "at most this much."

---
Tags: complexity-theory, time-complexity, big-o-notation
---


# Question
Title: Traveling Salesman Problem with Neural Network
I was curious if there were any new developments in solving the traveling salesman problem using something like a Hopfield recurrent neural network. I feel like I saw something about recent research getting a breakthrough in this, but I can't find the academic papers anywhere. Is anyone aware of any new, novel developments in this area?

# Answer
This Medium post lists the latest (not a full list of course) studies in the combinatorial optimization domain. All three papers use Deep Reinforcement Learning, which does not need any training set but learns completely from its own experience.

I have been working on the first paper for some time and inference time is on milliseconds level. According to their experiments, the approximation ratio (a metric they use to benchmark their own method) on 1000-1200 test cases reaches to 1.11.
> 7 votes

# Answer
there are *many* papers on using artificial neural networks to solve TSP including recurrent and Hopfield networks, and they "succeed" in a rough sense, but so far there does not seem to be any evidence that the techniques are in any way (strongly?) superior to other algorithmic approaches, so its something more like a research curiosity at the moment. the use of ANNs for this problem is indeed counterintuitive from the pov of combinatorial algorithmics and the mechanisms by which the problem inputs/ outputs are encoded are novel and tend to vary, and maybe are not yet so standardized. the authors seem maybe more interested in demonstrating "proof of concept" and a comparison with other algorithm types seems more rare (there is some in the last paper). see eg
> 8 votes

# Answer
I commented this on another answer, but I think it deserves its own answer. Some Google Brain fellows presented a method for solving TSP using an architecture reminiscent of seq2seq in the 2017 paper NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING. In the introduction, they call out a (1985) paper that uses Hopfield networks to solve TSP. So that idea has been around for a while.

Another answer mentioned the 2015 "Pointer Networks" paper. It did something similar to this paper, but it was a supervised algorithm - it needed labeled data. The 2017 paper doesn't require this (by using negative tour length as a reward signal in a reinforcement learning algorithm).

The heuristic "always bet on neural nets" hasn't let me down (but then again, I've never been through an AI winter).
> 3 votes

# Answer
I don't see any reason to expect Hopfield recurrent neural networks to help with the traveling salesman problem.

Neural networks are a form of machine learning, and they are effective when we have a labelled training set: a bunch of instances, where for each we know the input (the feature vector) and the correct label/classification/output. Machine learning is often useful for finding patterns when we're not sure exactly how to define what the right output is; "we know it when we see it".

In contrast, the traveling salesman problem is a combinatorial problem: we want to know the shortest route through a graph. There's no issue in defining or specifying what the right output is: it's a well-defined mathematical problem. There's no obvious reason to think machine learning would be useful for the traveling salesman problem.
> 0 votes

---
Tags: np-hard, neural-networks, traveling-salesman
---


# Question
Title: Context-free grammar for tautologies in one variable
> Construct a context-free grammar for the set of tautologies in $p$ \- that is, the set of formulae in $\\{p, \text{true}, \text{false}, \land, \lor, \lnot, (, )\\}$ which evaluate to $\text{true}$ for any assignment to $p$.

My first step is to construct a CFG for all propositional formulae: $$ S \rightarrow S \land S \mid S \lor S \mid ( S ) \mid \lnot S\mid p \mid \text{true } \mid \text{ false} $$

What can I do from here?

# Answer
Every formula in $p$ is equivalent to one of four formulas: true, false, $p$, $\lnot p$. This suggests having four different nonterminals, which generate exactly formulas which have this truth values. Calling these $T,F,P,N$, we have, for example, $$ T \to T \land T \mid T \lor S \mid S \lor T \mid P \lor N \mid N \lor P \mid (T) \mid \lnot F \mid \mathrm{true}, $$ where $S \to T \mid F \mid P \mid N$; this additional nonterminal is only used as shorthand.

In the same way, you can write rules that generate all tautologies over any fixed number of variables.
> 2 votes

---
Tags: context-free, propositional-logic
---


# Question
Title: Proof that $\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context free
I am to prove that $L :=\\{0^i1^{i^2}:i\in\mathbb{N}\\}$ is not context-free. I presume that I can do this with the Pumping Lemma and the word $0^p1^{p^2}$, where we assume for a contradiction that $L$ has a Pumping Length of $p$, and here's my attempt:

Let $0^p1^{p^2}=uxyzv$ such that $xz$ is non-empty, $xyz$ is of length $\le p$ and $ux^iyz^iv\in L$.

* **Case 1**: if $xyz$ is entirely within $0^p$ then $ux^2yz^2v = 0^p0^k1^{p^2}$ for some $k\>0$ and hence $ux^2yz^2v \notin L$.
* **Case 2**: if $xyz$ is entirely within $1^{p^2}$ then we get the same contradiction (with $0^p1^{p^2}1^k$).
* **Case 3**: suppose that $x = 0^i$, $z = 1^j$. Then $ux^0yz^0v=0^{p-i}1^{p^2-j}$.

Then I want to show that $(p-i)^2 \ne p^2-j$, but I'm not sure how to do this.

# Answer
> 1 votes
The simplest way to show that your language is not context-free is by reduction to unary alphabet. Suppose that your language were context-free. Then the language obtained by applying a homomorphism which deletes all $0$'s would also be context-free. This language is the unary language $L' = \\{ 1^{i^2} : i \notin \mathbb{N} \\}$. It is known that a unary language is context-free iff it is regular. You can prove that $L'$ isn't regular in any number of ways (for example, it is finite but its limiting density is zero).

If you are hell-bent on using the pumping lemma, then the following argument works. As you mention, the only interesting case is Case 3, in which $x = 0^i$ and $z = 1^j$. According to the pumping lemma, for every $t$ the word $ux^{1+t}yz^{1+t}v = 0^{p+ti} 1^{p^2+tj}$ must belong to $L$, that is, $p^2+tj = (p+ti)^2$. But $(p+ti)^2 = \Theta(t^2)$ whereas $p^2+tj = \Theta(t)$, so for large $t$ the two cannot be equal.

---
Tags: context-free
---


title: Akra-Bazzi method integral diverges

text:
# Question
Title: Akra-Bazzi method integral diverges
I want to solve this recursion:

$$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$

My attempt and issue:

None of the cases for master theorem apply here. I tried using Akra-Bazzi method (https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi\_method) with

$f(n) = \frac{n}{lg(n)}$

The derivative of $f(n)$ satisfies the condition for Akra-Bazzi: $$\frac{d}{dn} f(n) = \frac{1}{lg(n)} - \frac{1}{ln(2)\*lg^2(n)} = O(n)$$ Also I found that $p=1$ to satisfy the method's condition that $\frac{a}{b^p} = 1$.

Now the solution is given by this formula:

$$T(n) = \theta(n^p\*(1-\int\_{1}^{n} \frac{f(x)}{x^{p+1}} dx)$$

So I calculated the integral: $$\int\frac{f(x)}{x^{p+1}} dx = lg(lg(x)) + C$$, but with one of the limits being $1$ it **diverges**!

The weird thing is that according to Wolfram Alpha calculator, $T(n) = \theta(nlg(lg(n)))$.

So why is it true if the integral diverges? What am I getting wrong here?

# Answer
> 2 votes
Your recurrence isn't really defined for $n = 1$. This suggests using a different value for the lower bound in the integral. The formula given by Akra–Bazzi doesn't actually depend on the exact value of the lower bound that you choose – it can at most affect the big Theta constant or, in your case, some lower order term. If you choose any lower bound which is large enough, then the Akra–Bazzi formula gives you $\Theta(n\log\log n)$ as wanted.

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


title: Diagonalization argument for MAJORITY

text:
# Question
Title: Diagonalization argument for MAJORITY
For any language $A$, define a language $L\_{A}$ as:

$L\_{A} = \\{0^{n}: \text{Number of strings in $A$ of length $n$ is more than $2^{n-1}$} \\}$

I am trying to construct an $A$ such that $L\_{A} \notin P^{A}$. It should intuitively be true, as a polynomial time machine cannot query an exponential number of strings and check whether a majority of them belongs to a language.

The proof boils down to a diagonalization argument. But I am unsure on how to construct the sets.

# Answer
Let $T\_1,T\_2,\ldots$ be an enumeration of all timed polytime machines, machine $T\_i$ running in time $p\_i(n)$. We will construct $A$ in stages. At each stage, the truth value of $A$ is defined on only finitely many inputs.

Stage $i$ handles $T\_i$. Choose an input length $n$ such that (i) $A$ is completely undefined and (ii) $p\_i(n) \< 2^{n-1}$. Run $T\_i$ on $0^n$. Each time $T\_i$ queries some yet undefined string in $A$, answer arbitrarily and fix the value of this string in $A$. Since $p\_i(n) \< 2^{n-1}$, in particular $T\_i$ queries fewer than $2^{n-1}$ strings of length $n$. If $T\_i$ answered "Yes", then define all remaining strings of length $n$ to be *outside* $A$. If $T\_i$ answered "No", then define all remaining strings of length $n$ to be *inside* $A$. Either way, the machine $T\_i$ is wrong on input $0^n$.

After infinitely many steps, we have defined $A$ at infinitely many strings, but probably not all strings. Define $A$ arbitrarily on all remaining strings.

We note that the same proof works for every (time constructible) complexity class in which a machine cannot make at least $2^{n-1}$ queries on input of length $n$.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Amortized analysis - increment in ternary counter
What is the amortized analysis of increment action in a ternary counter that is initialized to 0?

# Answer
> 2 votes
The amortized cost per increment will be $O(1)$. In order to show it let's use the aggregate method.

```
0  - 000
1  - 001
2  - 002
3  - 010
4  - 011
5  - 012
6  - 020
7  - 021
8  - 022
9  - 100
10 - 101
11 - 102
12 - 110
13 - 111
14 - 112
15 - 120
...

```

We can notice that the bits in the 0th place are changing in every increment operation ($3^0$). The bits in the 1th are changing in every 3th increment operation ($3^1$). The bits in the 2th place are changing in every 9th increment operation ($3^2$). And so on.

The total number of changes equals to the sum of times that every bit has changed. Let's assume $n\lt 3^{k+1}$ for some $k$. So the total number of changes in $n$ increments is no more than $$n+\frac n3+\frac n9+\frac n{3^3}+....+\frac n{3^k} \< \frac32n$$ Assuming it takes $O(1)$ to perform the change of one bit and the associated bookkeeping, the total cost of the sequence is $O(n)$. So the amortized cost per operation is $O(n)/n= O(1).$

---
Tags: data-structures, amortized-analysis
---


# Question
Title: How do the bits of a certain emoji code for all the colors?
I am watching an introductory course on computer science. At one part, it starts talking about unicode and how the bits 11111011000000010. He states that that codes for a laughing/crying face emoji.

However, he later on talks about how the pixels are each created through a number of bytes.He says the bytes 72, 73 and 33 make light red, light green and light blue.

My question is, if there are so many bytes which make up all those pixels in an emoji, how do the bits 11111011000000010 represent all those pixels of colour?

# Answer
> 1 votes
That binary number does not contain the information about the pixels in the image which is used to show the emoji. It is only a number which, according to the Unicode standard, refers to that emoji. Every program which shows text (e.g. email reader, web browser, ...) must have a way to convert that number into the actual pixels. Usually, in modern computers, there is a *font* file, which contains all the information about the pixels of each character. So, when the program has to display the emoji, it accesses the file and reads the pixel data corresponding to the emoji, and sends those pixels to the screen.

Note that the Unicode standard does not specify what these pixels are, but only that they should represent, say, a "cake emoji". Every program might use a different font, showing the cake in a different way.

This also happens for regular characters. Unicode says that "A" is represented by number 65, but there are many fonts that can be used to show that "A".

---
Tags: binary
---


# Question
Title: Why can't DFA's have 0 exiting arrows for some input symbols?
Suppose you are in a middle of computation on a non accepting state and at this point, an input of 0 is rejected by the DFA. But, according to Sipser's formal definition, you must still draw an exiting arrow for input 0 from this nonaccepting state, which is just redundant. Why not draw no arrows at all for 0?

# Answer
> 9 votes
This is part of the (usual) definition of DFAs. It's hard to argue with a definition.

While it's hard to argue with a definition, one can ask why the object was defined in a certain way. Here one answer is that we want our automaton to always be at a particular state, whatever happens. In other words, we want the transition function to be a *function* rather than just a partial function. It is a matter of taste.

Some people allow the transition function to be partial, and still call the resulting model *DFA*, though this is probably less common than Sipser's definition. The two definitions are almost equivalent – accommodating a partial transition function takes at most one additional "sink" state.

# Answer
> -1 votes
In addition to what Yuval Filmus wrote, let me remark that the transition "function" not actually being a function but, rather, a partial function may impair the elegance of some proofs (or make them unnecessarily harder). Consider, for instance, the proof of the pumping lemma; in the usual definition, you let $p$ be the number of states and then take a word $w$ which the DFA accepts and is longer than $p$. The argument then is that, when you consider the trace of states which the automaton takes to accept $w$, there is at least one state that comes up twice (by the pidgeonhole principle). This is then used to derive a loop and, hence, pump the "middle" part of $w$.

This argument falls flat on its face when the transition function is partial. Then there is no guarantee the DFA does not stop and accept $w$ previously to running into the loop.

(Of course, here I am talking about the DFA accepting early whereas you were possibly referring to only nonaccepting states having incomplete transitions, but I am sure you get the idea.)

---
Tags: finite-automata
---


# Question
Title: How to compute function rolling averages maximum for each possible interval length?
I'm searching for a fast way to calculate

$$ g(k):=\max\_{0\<i\<T-k} {\frac{1}{k} \sum\_{j=i}^{i+k} f(j)}$$

for $ 0\<k \le T $ given some discrete function $f$ defined on $ \[0; T\]$.

Is there algorithm to do it faster then naive $O(n^2)$? If so, how?

# Answer
The usual approach to compute rolling function is to keep/recompute old data and on each step "add" new data and subtract the data going out of the window. So, you need to transform your sum function into updateSum one:

sum(i+1) = updateSum(sum(i), f(i), f(i+k+1))
> 1 votes

---
Tags: algorithms
---