# Question
Title: How do you calculate the running time using Big-O notatation?
I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod():

```
 Static int doIt(int n) {
           for ←1  100 do    -> 100
             for ←1   do    -> n x 100
                 ←1;←       -> 1
           while < do       -> lg n
          ←(+)/2           -> lg n/2
        end while
        end for
        end for

    }

 static int myMethod(int n) {
                   ←1
                  ℎ ( < ) {          -> lg n
                        ()            -> ?
                         ←×2             -> lg n
        }
             1;

}

```

For each of the line I have inserted the answer I think would be a logical value to put e.g "-\> 100". However I am not confident with the answer. These are the following questions that I would like to ask as well:

1. Does all while loop have a value of lg n?
2. If the doIt(n) method does not have a return statement, do we still add in part of calculation?
3. For the line with m \<- (m+j)/2, the value I have inputted is lg n /2. Is that correct or is it some other value?
4. Whenever multiplying by 2 or dividing by 2 is it always lg 2? what if n is multiplied by 3?

Thank You

# Answer
1. The while loop is executed $O(\log n)$ times (more precisely, $\Theta(\log n)$ times).
2. Yes. You account for every statement that is executed.
3. The line can $m \gets (m+j)/2$ can be executed in time $O(1)$, assuming that arithmetic operations take constant time. The overall time spent in one execution of the wile loop of the function `doIt(n)` is $O(\log n)$, since the number of its iterations is also $O(\log n)$ (and, more precisely, $\Theta(\log n)$).
4. This depends on the actual cost model you are using. Assuming that arithmetic operations take constant time, what you are probably thinking of is the number of divisions (resp. multiplications) by $2$ needed for $n$ to drop below (become larger than) some value $x \< n$ (resp. $x\>n$). If that's the case then the number of iterations is $O(\log n - \log x) \subseteq O(\log n)$ (resp. $O(\log x - \log n) \subseteq O(\log x)$. Multiplying/dividing by any *constant* greater than $1$ does not change the asymptotic time complexity (recall that $\log\_b a = \frac{\log\_2 a}{\log\_2 b}$, where $\log\_2 b$ is a constant in this scenario).
> 1 votes

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


# Question
Title: Is my recursive algorithm for Equivalent Words correct?
Here is my problem.

**Problem** Given two words and a dictionary, find out whether the words are equivalent.

**Input:** The dictionary, D (a set of words), and two words v and w from the dictionary.

**Output:** A transformation of v into w by substitutions such that all intermediate words belong to D. If no transformation is possible, output “v and w are not equivalent.”

I need to write both recursive and dynamic programming algorithm. As for recursion, I came up with this algorithm. Is it correct?

```
 EquivalentWordsProblem(v, w, D)
 1.m <- len (v)
 2.n <-  len (w)
 3.substitutions = [] #array to save substitutions
 4.if m != n:
 5.  return "v and w are not equivalent"
 6.else
 7.for i <- m to 1 <-1 do
 8.  for j <- n to j <- 1 do
 9.    if v[i] != w[j]:
 10.           substituted_word <- v[1…i-1]+v[j] #we substitute v[i] for w[j]
 11.              if substituted_word in D:
 12.                substitutions.append(substituted_word)
 13.                   return EquivalentWordsProblem(v[1…m-i], w, D) #recur on the string of length m - i
 14.   else:
         return EquivalentWordsProblem(v[1…m-1], w, D) #recur on the string decreasing its length by 1
 15.if len(substitutions) != 0:
 16.  return substitutions
 17.else
 18.   return (“v and w are not equivalent”)

```

# Answer
> 1 votes
Your algorithm is not correct. Here is a counterexample: $D$ contains the words $aa,bb,ac,bc$; $v=aa$; and $w=bb$.

A transformation is possible $(aa \to ac \to bc \to bb)$ but your algorithm won't find it.

---
Tags: algorithms, recursion, word-combinatorics
---


# Question
Title: Weighted Online Matching - randomized algorithms
Let's consider the edge weighted online matching problem.

The Vertices arrive online and reveal all their current edges and edge-weights $w\_e\>0$. The goal is to maximize the matchings weight. An edge can only be added once and irrevocably to the matching. As so often, we consider basically consider the setting from KVV.

It is obvious, that any deterministic algorithm can't be competitive against an oblivious adversary. Since any new edge could have arbitrary large weight.

Can a randomized algorithm improve upon this result?

# Answer
> 4 votes
A randomized algorithm cannot be constant-competitive in worst-case order. A proof using Yao's principle can be found here.

---
Tags: algorithms, randomized-algorithms, randomness, matching, online-algorithms
---


# Question
Title: Is there any official terminology about something like double quotes "" grammar?
In many programming language string is a token.

For example:

```
 token               ::= '"' string
                       | digit nat

 string              ::= char string
                       | '"'

 nat                 ::= digit nat
                       | ϵ

```

This is a LL(1) grammar for some programming language's toke grammar.

When parsing a `string`, there is no need to check follow set, because there is a `"` at the end of each `string`.

Comparing with `nat`, `string` is more easy to parse.

My question is

Is there any official terminology about this kind of grammar?

Thanks.

---

Editing:

There was some mistake in the original grammar, thanks @rici for pointing out my mistakes.

# Answer
FOLLOW sets are not used in the parsing of either `string` or `nat`. In both cases, the parser merely needs to determine if the input is in a set of valid symbols. In the case of `nat`, the valid symbols are digits; in the case of `string`, they are characters other than `"`. (In real languages, the parser would also be checking for `\`). But in both cases, a check is necessary, and there's no good criterion for saying one test is "simpler" than another. (In practice, both checks are likely to be a simple table lookup. So they're O(1).)

FOLLOW sets are only needed when the grammar contains ε productions. Even then, the parser's actions are not complicated. What is more complicated is building the parser, something which only happens once. It's not really that big of a deal, but it's sufficiently notable that "ε-free grammars" are a thing. I don't think there's any common vocabulary to describe the difference between explicitly and implicitly-terminated repetition, and any way the distinction will be very hard to define strictly. Your `string` would be parsed by a parser which used a different rule to collect the trailing `"`, and it's quite possible that the two parsers end up with the same implementation.
> 1 votes

---
Tags: terminology, formal-grammars, parsers
---


# Question
Title: Which is more efficient? lg(n+10^n) higher than 2^lgn
Based on the order by asymptotic growth rate which is more efficient?

# Answer
> 1 votes
Compute $\lim\_{n\to\infty}\frac{\log(n+10^n)}{2^{\log(n)}}$. This is

$$\begin{align}\lim\_{n\to\infty}\frac{\log(n+10^n)}{2^{\log(n)}}&=\lim\_{n\to\infty}\frac{\log(n+1+10^{n+1})-\log(n+10^n)}{1}\\ &=\lim\_{n\to\infty}\log\left(\frac{(n+1)+10^{n+1}}{n+10^n}\right)\\ &=\lim\_{n\to\infty}\log\left(\frac{(n+1)/10^n+10}{n/10^n+1}\right)\\ &=\log(10)\\ &\>1 \end{align}$$

where the first equation was using Stolz-Cesaro theorem (L'Hospital for sequences).

That this limit is larger than $1$ implies that for $n$ large enough $\log(n+10^n)$ becomes larger than $2^{\log(n)}$.

# Answer
> 1 votes
Roughly speaking:

$\begin{align\*} \log\_2 (2^n) &= n \\ \log\_2(10^n + n) &\> \log\_2(10^n) \\ &= n \log\_2 10 \end{align\*}$

As $\log\_2 10 = 3.3219$, the later is larger.

For rough comparisons, you can discard "lower terms" with impunity. In any case, often "asymptotic growth rate" applies only for very large $n$, and is usually meant to hide constant factors (check e.g. Hildebrand's "Short Course on Asymptotics" for details on the notation and manipulation techniques). If so, both are $\Theta(n)$, and more details are needed to compare fairly.

---
Tags: asymptotics
---


# Question
Title: Find the smallest group of numbers with sum bigger then $X$
Given a list of numbers $S$ where $0 \< s\_i \< 100$, find the minimum sum group of numbers with a sum bigger than $X$.
Each number can be used multiple times.

Ex: for $S = \[3,4.1\], X = 10$ the solution is $\[3, 3, 4.1\]$

Is it a known problem? What will be the best way of solving it?

For now, my best solution is to randomly pick numbers and repeat the process multiple times.

# Answer
> 2 votes
Assuming you are looking for $S' \subset S$ with minimal $\sum\_{x \in S'} x \> X$ like Steven suggested, then you should be able to reduce the problem to an instance of knapsack with weights $w\_i$ and costs $c\_i$ with $w\_i = c\_i = s\_i$ for every $s\_i \in S$ where the weight of the knapsack is bounded by $X$.

If the solution $K := \sum\_{x \in S'} x$ is not greater than $X$, you need to repeat the process by setting $X := X + \varepsilon$ where $\varepsilon$ is the minimal distance between any two subset sums of $S$ and running knapsack again until it yields a solution $K \> X$.

**Edit:** Turns out that finding $\varepsilon$ isn't an easy problem. I first assumed $\varepsilon$ is the minimum between any two numbers in $S$, which can be found by sorting the list and finding the minimum between two adjacent elements. This would yield a good approximation in most cases, but it might not be the optimal solution. If your problem statement uses $\geq$ instead of $\>$, transforming the problem into knapsack will yield an optimal solution, no repetitions required.

# Answer
> 1 votes
Let me assume that all involved numbers are positive integers and let $n=|S|$. From the comments to your question, I understand your problem as follows:

> Given a set $S = \\{s\_1, \dots, S\_n\\}$ find a multiset $S'$ such that (i) each element of $S'$ belongs to $S$,( ii) the sum $\sigma$ of the elements in $S'$ is larger than $X$, and (iii) $S'$ minimizes $\sigma$.

You can solve the above problem in time $O(nX)$ with a dynamic programming algorithm.

For an integer $w \< X$, let $OPT\[w\]$ be true ($\top$) if it is possible to select a group of numbers with a total sum of $w$, and false ($\bot$) otherwise.

For $w \< 0$ we have $OPT\[w\] = \bot$. Moreover $OPT\[0\]= \top$ and, for $w\>0$: $$ OPT\[w\] = \bigvee\_{i=1,\dots,n} OPT\[w-s\_i\]. $$

The minimum attainable sum $\sigma$ that is larger than $X$ is then: $$ \min\_{i=1,\dots,n} \min\_{\substack{j = X-s\_i+1, \dots, X \\ OPT\[j\]=\top}} (j+s\_i). $$

The actual group of numbers that sum to $\sigma$ can be found by retracing (backwards) the dynamic programming choices.

# Answer
> 1 votes
If each number can be selected once, it is exactly the knapsack problem (known to be NP-complete): Just turn it on its head, and ask for the numbers *left out*, they are the set with the largest sum less than $S - X$, where $S$ is the sum of all numbers. Exactly the knapsack problem.

---
Tags: subset-sum, summation
---


# Question
Title: Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?
This is taken from an old exam of my university that I am using to prepare myself for the coming exam:

Given is a language $\text{Goto}\_{17}^c \subseteq \text{Goto}$. This language contains exactly those $\text{Goto}$ programs in which no constant is ever above $17$ nor any variable ever above $c$.

$Goto$ here describes the set of all programs written in the $Goto$ language made up of the following elements:

With variables $v\_i \in \mathbb{N}$ and constants $c \in \mathbb{N}$
Assignment: $x\_i := c, x\_i := x\_i \pm c$
Conditional Jump: if(Comparison) goto $L\_i$
Haltcommand: halt

I am currently struggling with the formalization of a proof, but this is what I have come to so far, phrased very casually: For any given program in this set we know that it is finite. A finite program contains a finite amount of variables and a finite amount of states, or lines to be in. As such, there is a finite amount of configurations in which this process can be. If we let this program run, we can keep a list of all configurations we have seen. That is, the combination of all used variable-values and the state of the program. If we let the program run, there must be one of two things that happens eventually: The program halts. In this case, we return YES and have decided that it halts. The program reaches a configuration that has been recorded before. As the language is deterministic, this means that we must have gone a full loop which will exactly repeat now.

No other case can exist as that would mean that we keep running forever on finite code without repeating a configuration. This means after every step, among our list of infinite steps, there is a new configuration. This would mean that there are infinite configurations, which is a contradiction.

Is this correct? Furthermore, how would a more formal proof look if it is? If not, how would a correct proof look?

# Answer
> 2 votes
There is a finite number of different states (the set of values of the variables and the program counter). Your "limited goto programs" are just a (messy) way to describe a deterministic finite automaton.

Or just reason that the program states being finite, it is certainly possible to map out all possible non-looping computations (by something like a breadth first search of the graph of states and neighbours).

---
Tags: decision-problem, halting-problem, turing-completeness
---


# Question
Title: algorithm to find shortest path connecting EVERY node
I have received a problem to solve and I am not sure what algorithm to use.

TLDR; Find the shortest path to get to every node in a undirected graph

The problem states that one must visit every station in the shanghai metro in the shortest path possible. Interchange Stations ('edges') can be reused and you can start / stop anywhere.

I have created a lookup table that shows connected stations as well as the distance to travel (not shown)

```
"Xinzhuang": [
  "Waihuan Rd." : 1
],
"Waihuan Rd.": [
  "Xinzhuang": 2.2,
  "Lianhua Rd.": 3
],
"Lianhua Rd.": [
  "Waihuan Rd.": 4,
  "Jinjiang Park": 5,
],
"Jinjiang Park": [
  "Lianhua Rd.": 9.1,
  "South Railway Station": 10.3
],
"South Railway Station": [
  "Jinjiang Park": 4.1,
  "Caobao Rd.": 1.1,
  "Shilong Rd.": 2.5
],
...

```

I found this `leetcode` problem but it did not mention any specific algorithm and since it was `O(2^N * N)` I wondered if there was a faster method than BFS.

https://leetcode.com/problems/shortest-path-visiting-all-nodes/solution/

Since my graph is so big, I was going to reduce the lines with a single path to a single node.

**What algorithm can I use that will work in Polynomial time, OR has the least time complexity?**

# Answer
> 1 votes
There is no polynomial-time algorithm for your problem unless $P=NP$, since it captures the Hamiltonian path problem as a special case.

Moreover, unless the exponential time hypothesis fails, there is no $2^{o(n)}$-time algorithm for your problem, where $n$ is the number of vertices.

---
Tags: algorithms, graphs, time-complexity, graph-traversal
---


title: Enumerator for Word and Halting Problem

text:
# Question
Title: Enumerator for Word and Halting Problem
in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I was wondering what kind of grammar and enumerator could this be. And let the Wordproblem be $ L = \\{ \langle M, w \rangle | M \space is \space TM \space and \space w \in L(M) \\} $ and Halting Problem $ L = \\{ \langle M, w \rangle | M \space is \space TM \space and \space M \space halts \space on \space w\\} $

Ok for word problem: since there exists a sequence of $M\_i$ I would start with $M\_1$ and find all words for this TM and give them out. So if I have any TM is there a possibility to give all words out which are accepted by this TM? I probably would have to give all $w\_i$ to it and compute the first i words for i steps, then i+1 words for i+1 steps and so on for a sequence of computable words $w\_1, w\_2,.. \in \Sigma^\* $ Or maybe something like DFS on all configurations. This really sounds like that only for one TM this could go on forever. So I would need to start the second TM for the same period of time after a while... Seems as if something similiar could work for Halting Problem. Do you have any more refined thoughts on this one?

Greets,

Felix

# Answer
Let $\Sigma = \\{0, 1\\}$. Clearly $\Sigma^\*$ is enumerable. For the word problem you can proceed as follows.

* For each pair $(i,j) \in \mathbb{N}\_+^2$ in dovetail fashion:
    + Let $w\_i$ be the $i$-th word in $\Sigma^\*$.
    + Check whether $w\_i$ encodes a valid Turing machine $T$ (w.r.t. some fixed encoding). If not skip to the next iteration.
    + Simulate the Turing machine $T$ with input $w$ for at most $j$ steps.
    + If $T$ halts at the end of the $j$-th step, output $T$.

For the Halting problem you can do as follows:

* For each pair $(i, j, k) \in \mathbb{N}\_+^3$ in dovetail fashion:
    + Let $w\_i$ be the $i$-th word in $\Sigma^\*$.
    + Let $w\_j$ be the $j$-th word in $\Sigma^\*$.
    + Check whether $w\_i$ encodes a valid Turing machine $T$ (w.r.t. some fixed encoding). If not skip to the next iteration.
    + Simulate the Turing machine $T$ with input $w\_j$ for at most $k$ steps.
    + If $T$ halts at the end of the $k$-th step, output $\langle T, w\_j \rangle$.
> 1 votes

---
Tags: formal-languages, computability, formal-grammars, decision-problem, enumeration
---


# Question
Title: Consistent theory based on L and not(A->A) is a theorem
I am working on this problem in which I have a theory $T$ based on language $\mathcal{L}$ and the only information we have is that **T is consistent** and ***$\vdash \lnot(A \rightarrow A)$***. Given this information, how can I know if this theory is sound, complete and/or decidable?

My only guess is that I can say that $T$ is sound because since $T$ is consistent and we can derive ***$\lnot(A \rightarrow A)$*** from axioms and inference rules, ***$\lnot(A \rightarrow A)$*** is a theorem and because of that we can assume that $T$ is sound (because the premises and conclusions are true).

Am I correct? What else can I say about this theory?

Thank you!

# Answer
I'll assume that we're working in the context of classical propositional logic.

The first thing to point out is that $\lnot(A \rightarrow A)$ leads to a contradiction: ($A \land \lnot A$). Since propositional logic itself is consistent, it is impossible to derive a contradiction, so $\vdash \lnot(A \rightarrow A)$ is impossible.

So perhaps your intention was $T \vdash \lnot(A \rightarrow A)$. This can only happen if $T$ is itself inconsistent.

Given that $T$ is inconsistent, $T$ is vacuously complete (since an inconsistent theory can prove any formula) and decidable (for the same reason). As for soundness, it's a property of the logical system, not any particular theory like $T$. Propositional logic is sound.
> 2 votes

---
Tags: terminology, logic, first-order-logic, propositional-logic, theory
---


# Question
Title: How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?
How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? OR P = NP if NPC intersects with Co-NPC

# Answer
Proving $NP=co-NP$ doesn't necessarily mean that $P=NP$. Although, the other way around *is* correct: Assume $P=NP$, then $co-NP=co-P=P=NP$.
> 0 votes

# Answer
You won't find anything useful with our current knowledge. However, a change to $\Pi^c\in \mbox{P}$ will get you $\mbox{P}=\mbox{NP}$.
> 0 votes

---
Tags: complexity-theory, np-complete, np, polynomial-time, p-vs-np
---


# Question
Title: Why does the GS1 DataMatrix encode diagonally instead of vertically or horizontally?
Perhaps this is the wrong exchange, so if there is a better place to post this please tell me!

The DataMatrix encodes diagonally in a sort of zig zag pattern, as shown below.

Why don't they encode horizontally or vertically, like how it's done in QR Codes? If they did this it would appear to eliminate the need for confusing diagonal wrapping. QR code encoding algorithm for reference below:

# Answer
Not a full answer, but this AMS column considers the same question:

"The way in which bytes are stored as bitten squares might seem a bit peculiar, but if you think about how errors occur in the transmission of data matrices (for example poor printing, postage cancellation), it makes sense. The scheme is designed so that the minimum number of bytes are affected by such errors. Other features (the funny way in which \`unrandomization' is applied) are not so clearly advantageous, and are pretty much a mystery to me."

http://www.ams.org/publicoutreach/feature-column/fcarc-data-matrix
> 3 votes

---
Tags: information-retrieval
---


# Question
Title: If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?
I was studying automata theory and formal languages and came across this question:

If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ?

I've searched the theory but I am missing something. And I cant find the answer anywhere, so I am asking here.

Definitions:

$P$ = set of rules

Right-regular rule: grammar $G =(N,T,P,S)$, a rule is in $P$ if the rule is in the form: $A \rightarrow Ba$ $(A, B \in N) \wedge (a \in T)$

Left-regular rule: grammar $G =(N,T,P,S)$, a rule is in $P$ if the rule is in the form: $A \rightarrow aB$ $(A, B \in N) \wedge (a \in T)$.

Left-regular grammar: a grammar where all the rules are left-regular rules.

Right-regular grammar: a grammar where all the rules are right-regular rules.

Example of a rule set $P$ with both left-regular and right-regular rules: $P = \\{ A \rightarrow a, B \rightarrow b \\}$

And being both left-regular and right-regular makes the grammar regular and type 3

# Answer
Your grammar only contains rules of the form $A \to a$, for $A \in N$ and $a \in T$. Therefore $L(G) = \\{ \sigma \in T : S \to \sigma \in P \\}$. You take it from here.
> 0 votes

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


# Question
Title: Efficient algorithm to compute the $n$th Fibonacci number
The $n$th Fibonacci number can be computed in linear time using the following recurrence:

```
def fib(n):
    i, j = 1, 1
    for k in {1...n-1}:
        i, j = j, i+j
    return i

```

The $n$th Fibonacci number can also be computed as $\left\[\varphi^n / \sqrt{5}\right\]$. However, this has problems with rounding issues for even relatively small $n$. There are probably ways around this but I'd rather not do that.

Is there an efficient (logarithmic in the value $n$ or better) algorithm to compute the $n$th Fibonacci number that does not rely on floating point arithmetic? Assume that integer operations ($+$, $-$, $\times$, $/$) can be performed in constant time.

# Answer
> 23 votes
You can use matrix powering and the identity $$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F\_{n+1} & F\_n \\ F\_n & F\_{n-1} \end{bmatrix}. $$ In your model of computation this is an $O(\log n)$ algorithm if you use repeated squaring to implement the powering.

# Answer
> 7 votes
You can read this mathematical article: *A fast algorithm for computing large Fibonacci numbers* (Daisuke Takahashi): PDF .

More simple, I implemented several Fibonacci's algorithms in C++ (without and with GMP) and Python. Complete sources on Bitbucket. From the main page you can also follow links to:

* The C++ HTML online documentation.
* A little mathematical document: *Fibonacci numbers - several relations to implement good algorithms*

The most useful formulas are:

* $F\_{2n} = F^2\_{n + 1} - F^2\_{n - 1} = 2 F\_n F\_{n - 1} + F^2\_n$
* $F\_{2n + 1} = F^2\_{n + 1} + F^2\_n$

Be careful on algorithm. You must not calculate the same value several times. A simple recursive algorithm (in Python):

```
def fibonacci_pair(n):
    """Return (F_{n-1}, F_n)"""
    if n != 0:
        f_k_1, f_k = fibonacci_pair(n//2)  # F_{k-1},F_k with k = n/2

        return ((f_k**2 + f_k_1**2,
                 ((f_k*f_k_1)*2) + f_k**2) if n & 1 == 0  # even
                else (((f_k*f_k_1)*2) + f_k**2,
                      (f_k + f_k_1)**2 + f_k**2))
    else:
        return (1, 0)

```

Its complexity is logarithmic (if the basic operations are in constant time): $O(\log n)$.

# Answer
> 1 votes
We should first note that Fibonacci numbers $(F\_n)$ grow very fast with $n$ and cannot be represented in 64-bits for $n$ larger than 93. So a program for computing them for such $n$ needs to use additional mechanisms to operate on these large numbers. Now, considering only the count of (large-number) operations, the algorithm to sequentially compute them will require linear number of operations.

We can benefit from the below identity about Fibonacci numbers:

$ F\_{2m} = 2F\_mF\_{m+1}−{F\_m}^2$

$ F\_{2m+1}={F\_m}^2+ {F\_{m+1}}^2 $

So, if we know $F\_m$ and $F\_{m+1}$, we can directly compute $F\_{2m}$ and $F\_{2m+1}$.

Consider the binary representation of $n$. Observe that starting with $x=1$, we can make $x=n$ by iteratively doubling and possibly adding 1 to $x$. This can be done by iterating over the bits of $n$, and checking if it is 0 or 1.

The idea is that, we can maintain $F\_x$ in sync with $x$. In each such iteration, as we double $x$ and possibly add 1 to $x$, we can also compute the new value of $F\_x$ using the earlier value of $F\_x$ and $F\_{x+1}$, with above equations.

Since the number of iterations will be logarithmic in $n$, the total (large-number) operations are also logarithmic in $n$.

For further details, please refer section "Improved Algorithm" of this article (written by me).

# Answer
> 0 votes
Basic theory and code for computing linear recurrences with constant coefficients in $O(\log\_2 n)$ is available from http://www.jjj.de/.

Check the free book Matters Computational and the pari/gp code.

# Answer
> 0 votes
If you have to perform `q` queries asking `fib(n)` for multiple `n` values, you can use dynamic programming to solve it in O(`n + q`).

```
int dp[100];

int fib(int n){
    if(dp[n] != 0) return dp[n];
    dp[n] = fib(n - 1) + fib(n - 2);
    return dp[n];
}

```

The idea is to store already processed values so if the recurrence call that value, if returns in O(1).

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


# Question
Title: Proof for values of d with d:= ||L|| - N(L) with $d \in \mathbb{Z}$ and N(L) Nerode Index
Let ||L|| be the sum of all lengths of words in L und N(L) the number of equivalence claesses for the Relation $\equiv\_L$ from Myhill–Nerode theorem. Proof, which values d can have with $d:=||L||-N(L),d\in\mathbb{Z}$

Some conclusions I came up with so far:

* |L|| is infinite, when L is infinite. Then d is not defined.
* When N(L) is infinite for any non regular language, so L is infinite as well and $\infty - \infty $ wouldn´t be defined.
* So say ||L|| is finite then N(L) is finite as well because every word hase to be in a certain class. If not ||L|| would be infinite. Though when N(L) is finite, ||L|| doesn´t have to be finite since we might have some symbols looping over states.
* d is probably never negative, because if N(L) \> ||L|| we would have classes which don´t belong to words in L.
* When d = 0 then, N(L) = ||L|| and there would be a class for every word in L.

So d can be anything from $\\{ 0,...,\infty \\}$

Might this be enough for an answer or am I missing any cases/details? Where could I be proofing more formally?

# Answer
> 1 votes
In order to make the question nontrivial, you have to assume that $L$ is finite. You haven't specified what the alphabet is, so I will assume that the alphabet is arbitrary.

First, let us show that $N(L) \leq \\|L\\|+2$. We can construct a DFA for $L$ whose states consist of all prefixes of words in $L$, together with a failure state. This DFA contains an initial state (corresponding to the empty prefix), a failure state, and one state for every non-empty prefix. In particular, $$ N(L) \leq 2 + \sum\_{w \in L} |w| = 2 + \\|L\\|. $$ In other words, $d \geq -2$.

Second, let us consider the language $L\_\Sigma = \\{\sigma : \sigma \in \Sigma\\}$ over an alphabet $\Sigma$. The minimal DFA for this language contains three states, and so the value of $d$ for $L\_\Sigma$ is $$ \\|L\_\Sigma\\| - N(L\_\Sigma) = |\Sigma| - 3. $$ As $\Sigma$ ranges over all possible alphabets, we obtain all values which are at least $-2$.

---
Tags: formal-languages
---


# Question
Title: In the dataflow programming paradigm programs are modeled as directed graphs. Are the edges of the graph variables? And are the vertexes functions?
As I understand it in dataflow programming, programs are structured as directed graphs, an example of which is below

Is it true to say that the arrows (or edges) represent the variables within a program and the vertexes (blue circles) represent programmatic functions? Or is this too much of a simplification?

I am interested in understanding how dataflow languages actually apply graph theory.

# Answer
To be precise, the nodes represent the ***blocks*** (consisting a set of statements) and the edges represent ***possible data flow*** (the execution path).

Now basically the data flow analysis gives the information regarding the definition and use of data in the program (***Available Expression, Reaching Definition, Live variable***). This information is needed for code optimization.

And moving on to the graph theory applications in the compiler design, I would say ***Register allocation*** is the best example (Btw this can be done after gathering information from the data flow analysis).

This is a vast area, not easy to explain everything clearly. So, I would highly recommend to read a good book on compilers to get deeper insights
> 2 votes

---
Tags: graphs, programming-languages
---


# Question
Title: Maximization problem on finite collection of finite sets
## Problem

I am considering the following maximization problem:

* **Input** is a finite collection of finite sets $\mathcal{F} = \\{ X\_1, X\_2, \ldots, X\_n \\}$.
* **Goal** is to find a subset $G \subseteq \mathcal{F}$ that maximizes $|G| \times |\bigcap G|$ where
    + $|G|$ is the cardinality of the set $G$, and
    + $\bigcap G = \bigcap \\{X\_{i\_1}, X\_{i\_2}, \ldots, X\_{i\_m} \\} = X\_{i\_1} \cap X\_{i\_2} \cap \cdots \cap X\_{i\_m}$.

As an example, for the collection $$ \mathcal{F} = \\{ \\{a, b, c\\}, \\{a, b, c, x\\}, \\{b, c, y\\}, \\{a, b, c, z\\} \\}, $$ the maximizing subset is $G = \\{ \\{a, b, c\\}, \\{a, b, c, x\\}, \\{a, b, c, z\\} \\}$ and the score is $3 \times |\\{a, b, c\\}| = 9$.

Note: the score of $\mathcal{F}$ itself is $4 \times |\\{b, c\\}| = 8$.

## Question

I am planning to use a procedure of this problem for compressing data (represented by finite collections of finite sets). However, I don't have any good idea to solve this problem efficiently. As yow know, we can solve this by enumerating all the collections of $\mathcal{F}$; but, it's too slow for practical use.

Is there a polynomial-time or some kind of efficient algorithm for this problem? Or, does this problem belong to the complexity class that cannot be solved in polynomial time?

# Answer
> 3 votes
This problem is NP-complete. Let's reformulate it first: we have a bipartite graph, where

* The left side corresponds to elements
* The right side corresponds to sets
* The edge $(u,v)$ means that $u \in v$.

Our goal is to find the bipartite clique with the maximum number of edges. As stated in Rene Peeters, "The maximum edge biclique problem is NP-complete", the decision problem is NP-complete.

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


# Question
Title: Which is the best approach to solve Turing machines exercises?
I've this exercise of which I'm not very sure about my solution.

Exercise:

> Define the transition table about a Turing Machine that accepts words on the {a, b} alphabet where each a is followed by only two b.

My proposed solution is:

(f *stands for transition function*)

* f(q0, a) = (a, q1, R)
* f(q0, b) = HALT
* f(q1, a) = HALT
* f(q1, b) = (b, q2, R)
* f(q2, a) = HALT
* f(q2, b) = ACCEPT

I came up with this after thinking in the same way as finite state machines, even if I know are different with respect to Turing Machines (no tape, no reading/writing symbols and no right/left moves).

So, my question is, which is the best way of reasoning when I have to solve these kinds of problems?

Thank for your attention!

# Answer
There isn't really a "best way of reasoning". Mathematical proof is essentially a creative act and there isn't a straightforward recipe you can follow. I usually find it helps to treat Turing machine construction as a programming problem, which is basically what it is.
> 0 votes

# Answer
1. Understanding de problem: the statement says "where each a is followed by only two b", so I suppose any string of the form (abb)\* is valid.
2. This is a Regular Language, so you can make a Turing Machines that works **exactly** like a Finite Automaton. No need to go Left, no need to replace any symbol, no need to use extra slots.
3. To design a TM for a more complex language, you need to define an strategy first. How are you going to mark slots and to go left and right to solve your problem? Of Course, this could be not trivial.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Difficulty in few steps in proof of "Amortized cost of $\text{Find-Set}$ operation is $\Theta(\alpha(n))$"assuming union by rank, path compression
I was reading the section of *data structures for disjoint sets* from the text *Introduction to Algorithms* by *Cormen et. al* .I faced difficulty in understanding few steps in the proof of the lemma as given in the question title. Here we assume we follow union by rank and path compression heuristics. Before we move into our target lemma a few definitions and lemma is required as a prerequisites for the target lemma.

---

(**Note**:*Below are prerequisites of the proof where I am facing difficulty ; as the proof refers to them , so I mention the below blockquote; my doubts however start after the following blockquote*.)

The prerequisites:

> $$level(x)=\max\\{k:rank\[p\[x\]\]\geq A\_k(rank\[x\])\\}$$ $$iter(x)=\max\\{i:rank\[p\[x\]\]\geq A\_{level(x)}^{(i)}(rank\[x\])\\}$$ $$\phi\_q(x) = \begin{cases} \alpha(n).rank\[x\] &\quad\text{if $x$ is a root or $rank\[x\]=0$ }\\ (\alpha(n)-level(x)).rank\[x\]-iter(x) &\quad\text{if $x$ is not a root and $rank\[x\]\geq1$ }\\ \end{cases}$$
>
> > Corollary 21.5 : As we follow the path from any node toward a root, the node ranks strictly in- increase. ■
>
> > Lemma 21.9 : Let $x$ be a node that is not a root, and suppose that the $q$ th operation is either a $\text{Link}$ or $\text{Find-Set}$. Then after the $q$th operation, $\phi\_q(х) \leq \phi\_{q-1}(х)$. Moreover, if $rank\[x\] \geq 1$ and either $level(x)$ or $iter(x)$ changes due to the $q$ th operation, then $\phi\_q(х) \< \phi\_{q-1}(х) - 1$. That is, $x$'s potential cannot increase, and if it has positive rank and either $level(x)$ or $iter(x)$ changes, then $x$'s potential drops by at least $1$.■
>
> $$\alpha(n) : \text{Inverse of a very fast growing function $A\_k(j)$}$$

---

Now in the proof below I marks the steps where I face problem

> > Lemma 21.12: The amortized cost of each $\text{Find-Set}$ operation is $\Theta(\alpha(n))$.
>
> Proof: Suppose that the $q$ th operation is a $\text{Find-Set}$ and that the find path contains $s$ nodes. The actual cost of the $\text{Find-Set}$ operation is $O(s)$. We shall show that no node's potential increases due to the $\text{Find-Set}$ and that at least $\max\\{0,s - (\alpha(n) + 2)\\}$ nodes on the find path have their potential decrease by at least $1$.
>
> To see that no node's potential increases, we first appeal to **Lemma 21.9** for all nodes other than the root. If $x$ is the root, then its potential is $\alpha(n) . rank\[x\]$, which does not change.
>
> Now we show that at least $\max\\{0,s - (\alpha(n) + 2)\\}$ nodes have their potential decrease by at least $1$. Let $x$ be a node on the find path such that $rank\[x\] \> 0$ and $x$ is followed somewhere on the find path by another node $у$ that is not a root, where $level(y) = level(x)$ just before the $\text{Find-Set}$ operation. (Node $у$ need not immediately follow $x$ on the find path.) $\require{color}\colorbox{yellow}{All but at most $\alpha(n) + 2$ nodes on the find path satisfy these constraints on $x$.}$ $\require{color}\colorbox{yellow}{Those that do not satisfy them are the firstnode on the find path (if it has rank $0$),}$ $\require{color}\colorbox{yellow}{ the last node on the path (i.e., the root), and the last node $w$ on the path for which}$ $\require{color}\colorbox{yellow}{ $level(w) = k$, for each $k = 0,1,2,..., \alpha(n) - 1$.}$
>
> Let us fix such a node $x$, and we shall show that $x$'s potential decreases by at least $1$. Let $k = level(x) = level(y)$. Just prior to the path compression caused by the $\text{Find-Set}$, we have
>
> $rank\[p\[x\]\] \geq A\_k^{(iter(x)}(rank\[x\])$ (by definition of $iter(x)$) ,
>
> $rank\[p\[y\]\] \geq A\_k(rank\[y\])$ (by definition of $level(y)$ ,
>
> $rank\[y\] \> rank\[p\[x\]\]$ (by *Corollary 21.5* and because $у$ follows $x$ on the find path)
>
> Putting these inequalities together and letting $i$ be the value of $iter(x)$ before path compression, we have
>
> $rank\[p\[y\]\] \geq A\_k(rank\[y\]) \geq A\_k(rank\[p\[x\]\])$ (because $A\_k(j)$ is strictly increasing) $\> A\_k(A\_k^{(iter(x)}(rank\[x\])) = A\_k^{(i+1)}(rank\[x\])$ .
>
> Because path compression will make $x$ and $у$ have the same parent, we know that after path compression, $rank\[p\[x\]\] = rank\[p\[y\]\]$ and that the path compression does not decrease $rank\[p\[y\]\]$. Since $rank\[x\]$ does not change, after path compression we have that $\require{color}\colorbox{pink}{$rank\[p\[x\]\]\geq A\_k^{(i+1)}(rank\[x\])$. Thus, path compression will cause either $iter(x)$ to }$ $\require{color}\colorbox{pink}{increase (to atleast $i + 1$) or $level(x)$ to increase (which occurs if $iter(x)$ increases}$ $\require{color}\colorbox{pink}{to at least $rank\[x\] + 1$). In either case,by Lemma 21.9, we have $\phi\_q(х) \leq \phi\_{q-1}(х) - 1$.}$ $\require{color}\colorbox{pink}{Hence, $x$'s potential decreases by at least $1$.}$
>
> The amortized cost of the $\text{Find-Set}$ operation is the actual cost plus the change in potential. The actual cost is $O(s)$, and we have shown that the total potential decreases by at least $\max\\{0,s - (\alpha(n) + 2)\\}$. The amortized cost, therefore, is at most $O(s) — (s — (\alpha(n) + 2)) = O(s) — s + 0(\alpha(n)) = O(\alpha(n))$, since we can scale up the units of potential to dominate the constant hidden in $О (s)$. ■

---

In the proof above I could not get the mathematics behind the statements highlighted in yellow and pink. Can anyone help me out?

---

The corresponding portion of the text can be found here

# Answer
Best analysis I've seen is by Seidel and Sharir "Top-Down Analysis of Path Compression" (SIAM J. Computing 34:3, 515-525 (2005). Still heavy going...

Easier to digest is Ericson's chapter in his "Algorithms".
> 1 votes

---
Tags: algorithm-analysis, data-structures, amortized-analysis, union-find, disjoint-sets
---


# Question
Title: Are all Recursively Enumerable languages which are not Recursive also Undecidable?
Knowing that all Recursive languanges are Decidable and All Not R.E. Languages are Undecidable (correct me if I am wrong), Are all languages which are R.E. but not Recursive also Undecidable?

R.E. ==\> Recursively Enumerable

# Answer
> 1 votes
A language is *recursive* (newer terminology: computable, also decidable) is there is a Turing machine that always halts that recognizes the language. It is *recursively enumerable* (new: computably enumerable) if there is a Turing machine that accepts it (it halts and accepts for strings in the language, it might never halt for strings not in the language). If the language is not recursive, it isn't decidable ("recursive" and "decidable" are alternative terms for the same class of languages).

---
Tags: computability, undecidability
---


# Question
Title: What is the reason for writing parallel programs?
Why do programmers write parallel programs instead of giving them the ability to automatically convert from serial to parallel?

# Answer
Because the technology to extract paralellism automatically from sequential programs is still woeful... yes, some compilers/languages do take a stab at the problem, but for really demanding applications it still pays off to do the job manually.
> 1 votes

---
Tags: parallel-computing
---


title: Uncurrying and Polymorphism

text:
# Question
Title: Uncurrying and Polymorphism
How do we uncurry functions when they are polymorphic? For example, is it possible to uncurry the following types? If so what is the uncurried type?

1. $\forall X. X \rightarrow int \rightarrow X$ ?
2. $int \rightarrow \forall X. X \rightarrow X$ ?
3. $int \rightarrow \forall X. X \rightarrow int \rightarrow X$ ?

# Answer
The other answers are good, I just wanted to make it explicit that currying for dependent types is $$ \textstyle \prod (x : A) . \prod (y : B(x)) . C(x, y) \ \cong \ \prod (p : \sum (x : A) . B(x)) . C(\pi\_1(p), \pi\_2(p)) $$ which is more suggestive in Agda-style notation: $$ (x : A) \to (y : B(x)) \to C(x,y) \ \cong\ (p : (x : A) \times B(x)) \to C(\pi\_1(p), \pi\_2(p)) $$ In your case, replace $\Pi$ and $\Sigma$ with $\forall$ and $\exists$.
> 4 votes

# Answer
The uncurrying process will lead to existential types. Since the adjoint of $(X\to)$ is $(X\times\vphantom{Y})$ and the adjoint of $(\forall X.)$ is $(\exists X.)$, it is appearently inevitable. Also, it will lead to types depending on terms (where simple types only depends on types themselves, and polymorphism allows terms to depend on types). So generally it is not doable in your restricted type system.

Let's write these in more suggestive notations. The usual currying/uncurrying converts between $X \to Y \to Z$ and $X \times Y \to Z$. But the former can be written in the product notation: $\prod\_{x:X} \prod\_{y:Y} Z$, where $\prod\_{y:Y}Z$ means the product of many copies of $Z$, one for each element $y$ of $Y$, which is a function from $Y$ to $Z$. The latter can be written as $\prod\_{p:X\times Y} Z$. And $A \times B$ can be rewritten as $\sum\_{a:A}B$, which is the sum of many copies of $B$, one for each element $a$ of $A$.

This notation is easily generalized to polymorphic types (or even more generally, dependent types), simply by allowing the inner expression to depend on the variable: $\prod\_{X : \*} X \to A$ means the product of $X \to A$ for every type $X$. So we can make the more general currying/uncurrying process: $$\prod\_{x:X}\prod\_{y:Y\_x} Z\_{x, y} \Leftrightarrow \prod\_{p:\sum\_{x:X} Y\_x} Z\_{\pi\_1(p), \pi\_2(p)},$$ where $\pi\_i(p)$ is the projection that selects the $i$-th element.

---

Back to the question itself. The first one is actually a function of three arguments. So just turning it into $\forall X. (X\times \mathtt{int}) \to X$ is just uncurrying the second and third argument. The uncurried form neccesarily involves dependent types: $\forall (p:\exists X. X\times \mathtt{int}). \pi\_1(p)$. The rest can be done similarly.
> 2 votes

# Answer
I can only think of some uncurrying of 1 and 3.

1. $\forall X. (X \times int) \rightarrow X$
2. It looks like we can not uncurry this one, unless we transform it first into the isomorphic type 1.
3. $int \rightarrow \forall X. (X \times int) \rightarrow X$

Alternatively, if we can apply an isomorphism, (3) can be rewritten as $$ \forall X. int \rightarrow (X \times int) \rightarrow X $$ and then, by uncurrying $$ \forall X. (int \times X \times int) \rightarrow X $$

---

In my view, it is more interesting when we also have existential types in the calculus and the returned type does not involve $X$. E.g., we can perform a kind of uncurring on $$ \forall X. X \rightarrow (X \rightarrow int) \rightarrow int $$ and get $$ (\exists X. X \times (X \rightarrow int)) \rightarrow int $$ which is isomorphic to $$ int \rightarrow int $$
> 1 votes

---
Tags: programming-languages, lambda-calculus, functional-programming, polymorphisms, higher-order-logic
---


title: Counting circuits with constraints

text:
# Question
Title: Counting circuits with constraints
Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).

In order to show that there are boolean functions $f : \\{0,1\\}^n \rightarrow \\{0,1\\}$ which can be computed only using circuits of size $\Omega(2^n/n)$, we use a counting argument: there are at most $O(2^{k \log k})$ circuits of size $k$, and $2^{2^n}$ such functions.

Suppose that I am interested in counting circuits of size $k$ that compute different functions. The "simple" counting argument won't work since it may be possible that two "syntactically" different circuits actually compute the same function. In other words, I want to bound the size of the set: $$F = \\{ f: \\{0,1\\}^n \rightarrow \\{0,1\\} | f \text{ can be computed using a circuit of size }k \\} $$

Then $|F| \< $ the number of circuits of size $k$ (since any circuit computes one function), but how can I bound $|F|$ from below? (i.e. $ x \<|F|$)

# Answer
In order to bound the number of functions computed by circuits of size $k$, you have at least two options:

* Construct a large number of circuits of size $k$, which by construction compute different functions.
* Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function.

As an example, it is known that every function on $m$ variables can be computed by a circuit of size $O(2^m/m)$. By considering functions of the form $f\_1(x\_1,\ldots,x\_m) \lor \cdots \lor f\_{n/m}(x\_{n-m+1},\ldots,x\_n)$, this shows that there are at least $(2^{2^m})^{n/m}$ different functions computed by circuits of size $k = O(n2^m/m^2)$. In terms of $k$, the number of functions is roughly exponential in $k\log k$, for $m \gg \log n$.
> 1 votes

---
Tags: complexity-theory, combinatorics, circuits, lower-bounds
---


# Question
Title: If $A$ is context-free then $A^*$ is regular
I am currently studying for my exam and I am having trouble to solve this question:

> Right or wrong: If $A$ is context-free then $A^\*$ is regular.

I think it's wrong because if $A$ is context-free it means that $A$ can be a non-regular language. And the non-regular languages are not closed under the Kleene star operation (at least I think so). I am not sure how write this in a more formal way.

Maybe like this?

Let $A=\\{a^nb^n \mid n \in \mathbb{N}\\}$. Then we know that $A$ is non-regular and context-free. However, I'm not sure what $A^\*$ is.

# Answer
> 3 votes
Let $A=\\{a^nb^n \mid n \in \mathbb{N}\\}$. Then we know that $A$ is non-regular and context-free. Also we can see that $A^\*\cap a^\*b^\*=A$. Since $a^\*b^\*$ is a regular expression, we do know that it is regular. Lets assume that A\* is regular.

The regular languagues are closed unter intersection. Therefore $A^\*\cap a^\*b^\*$ must be also regular(because we assume that $A^\*$ is regular). This would implicate that A is regular because $A^\*\cap a^\*b^\*=A$. This is a contradiction because we know that A is not regular. Therefore A\* cant be regular.

$q.e.d$

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


# Question
Title: Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?
For example, a valid number would be 6165156 and an invalid number would be 1566515.

I have tried many times to construct a finite state machine for this with no success, which leads me to believe the language is not regular. However, I am unsure how to formally prove this if that is indeed the case. I tried applying the pumping lemma but I am not completely sure how to apply it to this particular language.

Any help is appreciated!

# Answer
I attempted to solve the question separately:
The "no more than two 5s" bit can be represented by the regex $a^\*(\epsilon+5)a^\*(\epsilon+5)a^\*$.
The "no two 6s in a row" bit can be represented by the regex $(a+6a)^\*(6+a+\epsilon+6a)$.
Where $a\in\\{1,2,3,4,7,8,9,0\\}$.
Notice that we could potentially replace all the a\*s in the first regex with the second regex, but this is problematic since it would allow double 6s. So I drew a FSM that uses this idea without violating the constraints. Hopefully, you could work out the regex and minimize the FSM if it can be minimized.
The language is regular since an FSM that defines it exists, hence its regular expression can be obtained.
> 0 votes

# Answer
"At most two 5" is regular (draw the DFA, the idea is to count 5 and accept anything that has less than three of them).

"No two adyacent 6" is also regular. Again, to draw the DFA, make sure after a 6 there is something else.

So both the above are regular, and regular languages are closed with respect to intersection (i.e., abide by both rules).
> 0 votes

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


title: Is $EVEN-SAT$ $NP$-hard?

text:
# Question
Title: Is $EVEN-SAT$ $NP$-hard?
I'm looking for an $NP$-hardness proof for the following variant of $SAT$:

$$ EVEN-SAT = \\{\langle \phi \rangle: \phi \text{ has an even number of satisfying assignments}\\} $$

I've been playing around with gadgets for a while, but I haven't been able to construct a reduction. Still, I feel like there should be one. Help!

# Answer
> 3 votes
$\textsf{EvenSat}$ is $\oplus P$-Complete (pronounced "Parity $P$"). The way to see this is (i) that it is the complement of $\textsf{OddSat}$, which is "the" natural $\oplus P$-Complete problem in the same way $\textsf{Sat}$ is "the" natural $\mathcal{NP}$-Complete problem, and (ii) $\oplus P$ is closed under complement.

The Valiant-Vazirani Theorem gives a randomized Cook reduction (i.e., a many-one reduction) with a one-sided error probability of $\mathcal{O}(1/n)$ from $\textsf{Sat}$ to $\textsf{EvenSat}$. That is, $\textsf{EvenSat}$ is $\mathcal{NP}$-Hard under randomized reductions. This is why the Valiani-Vazirani Theorem is usually stated as $\mathcal{NP}\subseteq \mathcal{RP}^{\oplus P}$.

We have $\mathcal{RP}^{\oplus P}\subseteq P^{\\#P}$, so VV's Theorem is a bit tighter than what you would get from Toda's Theorem.

It is unlikely that $\textsf{EvenSat}$ is $\mathcal{NP}$-Complete, because then the polynomial hierarchy collapses to the first level, $PH=NP$. It is an open question whether $NP$ and $\oplus P$ are comparable, so far there is only oracle evidence that they are incomparable. (I don't know whether it is generally conjectured that Valiant-Vazirani can be derandomized from $\mathcal{NP}\subseteq\mathcal{RP}^{\oplus P}$ to $\mathcal{NP}\subseteq \mathcal{P}^{\oplus P}$. In that case, since $P^{\oplus P}=\oplus P$, we would have $\mathcal{NP}\subseteq \oplus P$. If I read \[1\] correctly, then it is *not* generally conjectured, since it would collapse the polynomial hierarchy)

\[1\] Dell, Holger, et al. "Is Valiant–Vazirani’s isolation probability improvable?." computational complexity 22.2 (2013): 345-383.

# Answer
> 2 votes
It is known that $NP \subset P^{\\#P}$ according to Toda's theorem but right now your question "NP hardnes of even SAT" is an open problem. We know that $NP \subset BPP^{mod\_2 SAT}$

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


# Question
Title: Intuition for Church-Turing thesis for Turing machines
I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion -- holds for mu-recursion. It reflects exactly the type of algorithms that *I* can carry out with my own brain.

I cannot see an analogous intuition for understanding why the Turing machine can execute any physically computable algorithm -- i.e. how did Turing "see" that the Turing machine was a good definition to use? Is there a good way to "imagine" the algorithms I perform in terms of the Turing machine, as opposed to general recursion as I am used to?

# Answer
> 3 votes
Imagine you are performing a computation by hand with a pencil and a stack of paper. \[1\] There is a limit on how many pieces of information you can keep in working memory at a time (sometimes claimed to be seven plus or minus two). So when you can't keep everything in your head, you write some of it down on a sheet of paper. And when you fill up a sheet, you put it in a pile for later reference and pull out another sheet. But there is a limit on how many sheets of paper you can look at at a time, too; you will have to flip between sheets as you work.

Turing machines are an abstraction of this idea of *local* computation. A Turing machine can write down as much auxiliary information as it wants, but it can only look at a finite amount of it at a time. A Turing machine head is like your brain's working memory—it can only store so much *stuff* before it has to write it down somewhere to avoid forgetting it.

The Church-Turing thesis says that any physically realizable computation does not require any "essentially nonlocal" operations. That is, any physically realizable computation can be broken down into a series of steps, each of which operates on $O(1)$ bits of information; there is no primitive operation that requires, say $O(n)$ arguments and cannot be reduced to operations with fewer arguments. \[2\] Or: anything you can compute in the real world can be computed given an unlimited stack of pencils and paper.

---

\[1\] Recall that the word "computer" in Turing's time referred to a human profession!

\[2\] A primitive operation that accepts an unbounded number of arguments is exactly what the oracle in an oracle Turing machine provides—hence why oracle machines can be more powerful than Turing machines.

# Answer
> 0 votes
I'll try to recount the history I understand of this but I'm not an expert on the history of mathematics. I think the early history of this issue is key. I'd also like to point out that I think I have some details wrong but the big picture right. I'd appreciate corrections and/or citations from people.

So, our story starts off with Hilbert's problems. A lot of Hilbert's problems deal with computation. Funny enough, at this time, there was no definition of what "computation" was! There was no mathematical model of what a computer was.

Many attempts were made. For a bit people wondered if primitive recursion might be the ticket but we found mechanically computable functions that were not primitive recursive like the Ackerman function. Still we *knew* that the primitive recursive functions could be computed with a physical machine so we at least had that.

Eventually Alonzo Church proposed the lambda calculus as a universal model of computation. Church started a correspondence with Kurt Godel (of incompleteness theorem fame). Godel did not believe that the lambda calculus was a universal model of computation. Godel proposed an alternative definition which was essentially the mu-recursive functions which I believe at the time he just called "the recursive functions". Godel had defined a set of functions from natural numbers to natural numbers dubbed "the recursive functions". Alonzo made a bet with Godel that he could prove the two models equivalent. After some correspondence Alonzo produced a proof. Godel's reaction was not to accept that both were valid models but to instead assume his recursive functions were not a sufficient model. It's hard to say what the intuition of these two giants was telling them at the time. They neither had our insight into computation but they were also geniuses who had studied such issues deeply, I don't really feel I can place myself in their shoes frankly. Clearly each had an intuition that their models of computation were "the" model of computation but this intuition didn't pass for mathematics.

Along came Allen Turing who produced the Turing machine model. I've heard that this model, aside from being described like a machine, was meant to be a model of how a human would do computation on paper. Regardless the important point is that there was a written down philosophical argument and intuition for *why* Turing machines captured the notion of computation. Turing proved that Turing machines were equivalent to these models (presumably by proving Turing machines equivalent to the lambda calculus given that Alonzo was Allen's advisor roughly around this period).

This proof, that all three models of computation, were equivalent, together with the collective intuitions of why these models of computation are complete, finally convinced Godel. These three, really just via some letters between each other, all had different intuitions. For many, including Godel and Turing, Turing machines were the most obviously complete model. At some point in these discussions however, Godel certainly found mu-recursive functions to be intuitively universal. I'm not sure any one ever thought the lambda calculus was intuitively universal but Alonzo and Kleene seemed to gain this intuition via working with Church encodings and other ways of computing, gained this intuition (I'm not sure when the fixed point combinator was discovered but this seems somewhat critical to me?).

So frankly, I'm not sure there's a great way to answer your question. Intuition on these is clearly different for everyone. I find Turing machines mostly intuitive but also I think the lambda calculus is intuitively universal after being shown the fixed point combinator and many examples of its use. You're just different from me and that's ok!

My best description of the intuition for Turing machines (I've forgotten my original source for this framing but it is not mine): Computation used to be something you did with a pencil. You'd write symbols down in an orderly way on a piece of paper, maybe cross some things out, write some new things down etc... Any computable function can be carried out by a human with a finite amount of paper essentially. Paper is of course 2D but what matters is the relative locations of the symbols and that they're unique so a Turing machine should be able to simplify it self and only use a 1D peice of paper. Surely anything you can write in 2D paper, you can translated to a 1D setting right? Now in this 1D setting you move though different steps of the algorithm, look at different parts of the tape to determine what step to do next, and then you eventually write a symbol down and move on to the next step. Turing machines capture exactly this kind of behavior. Steps are really just like states, moving the read-write head along the tape is like scanning your eyes across the paper, and writing a symbol down at a location is no different than you using a pen or pencil. There is clearly a machine that could do this and it seems intuitive that any algorithm you could carry out on pen and paper as a human could be captured by such a machine. I can't say weather this was the idea Turing had in mind but maybe it helps? Turing's intuition for this might be stated in his original paper if your curious (I've never actually read it).

---
Tags: turing-machines, turing-completeness, church-turing-thesis, mu-recursion
---


# Question
Title: A monad is just a monoid in the category of endofunctors, what's the enlightenment?
Pardon the word play. I'm a little confused about the *implication* of the claim and hence the question.

**Background:** I ventured into Category Theory to understand the theoretical underpinnings of various *categorical constructs* and their relevance to functional programming (FP). It seems (to me) that one of the "crowning gems" at the intersection of Cat and FP is this statement:

`A monad is just a monoid in the category of endofunctors`

What is the *big deal* about this observation and what are its programmatic/design implications? Sources like sigfpe and many texts on FP seem to imply the *mindblowingness* of this concept but perhaps I'm unable to see the subtlety that's being alluded to.

Here's how I understand it:

Knowing something is a monoid allows us to extrapolate the fact that we can work within a map-reduce setting where the associativity of the operations allows us to split/combine the computation in arbitrary order i.e., `(a1+a2)+a3 == a1+(a2+a3)`. It can also allow one to distribute this across machines and achieve high parallelization. (Thus, I could mentally go from a `theoretical construct -> computer science understanding -> practical problem solving`.)

For me it was *obvious* (as a result of studying Cat) to see that monads have a *monoidal* structure in the category of endofunctors. However, what is the implication one can draw from this and what is its programmatic/design/engineering impact when we're coding with such a mental model?

Here's my interpretation:

* **Theoretical Implication:** All computable problems at their heart are *monoidal* in a sense.
    + Is this correct? If so, I can understand the *enlightenment*. It's a different perspective on understanding the notion/structure of computable problems that wouldn't be obvious if coming from only a Turing/Lambda model of computation and I can be at peace.
    + Is there more to it?
* **Practical Implication:** Is it simply to provide a case for the `do-`notation style of programming? That is, if things are monoidal we can better appreciate the existence of the `do/for` constructs in Haskell/Scala. Is that it? Even if we didn't know about the monoidal underpinnings, we needn't *invoke* the *monoidalness* to make this claim since bind `>>=` and `flatMap` constructs are defined to be associative. So what gives? Or is it more to do with the *foldability* of monadic constructs and *that* is the indirect *enlightenment* that is being alluded to?

**Question(s):** What am I missing here? Is it simply the *recognition* of the fact that monads are generalized monoids and that they can be *combined* in any order similar to map-reduce operations like monoids? How does knowing about the monoidal property help *improve* the code/design in any way? What's a good example of before/after to show this difference (before knowing about monads/monoidality and after)?

# Answer
> 10 votes
This answer may not be exactly what you are looking for. That is, I think perhaps the importance of this characterisation is being overemphasised here. The quote

> a monad in X is just a monoid in the category of endofunctors of X

is originally from Mac Lane's *Categories for the Working Mathematician*, where it appears as a helpful intuition for the definition of monad, which, alone, can seem quite unfamiliar at first. By characterising it as a monoid in a particular monoidal category, the reader is given an alternative perspective. Note that the chapter on monads actually comes before the chapter on monoidal categories: the remark is intended to be helpful, rather than precise (it is made precise only later).

The quote was then rephrased in James Iry's infamous article Brief, Incomplete and Mostly Wrong History of Programming Languages.

> A monad is just a monoid in the category of endofunctors, what's the problem?

Presented out of context, as it is in the article, it is meant to amuse. The quote has since become a meme in the functional programming community, primarily because it is amusing, rather than a key insight for functional programming (though it does also serve to pique the curiosity of functional programmers, drawing them into the wonderful world of category theory). My view is that this characterisation, while helpful and interesting, is not as important as one might imagine from its popularity.

However, this is not to say there is no insight to be gained from this characterisation. First, let me point out that, while the presentation of a monad with a multiplication and unit is clearly suggestive of a monoid, as you point out, the Kleisli presentation, with a bind and return operation, is not. It is the Kleisli presentation that is common in functional programming, so certainly the characterisation as a monoid is more interesting from this perspective.

From a theoretical perspective, one of the insights is indeed that many natural structures in computer science (and mathematics) are monoidal. From the perspective of monads (particularly with their relation to cartesian operads and Lawvere theories), monoidal structure corresponds to substitution structure (equivalently, composition structure). Substitution is ubiquitous in computer science (for example, capture-avoiding substitution in a type theory, or grafting of trees). Monads are just one more example.

While understanding formally the statement in question may not be enlightening, I suggest that it is enlightening to understand the different perspectives on monads, as it allows you to see the different ways in which monads might be used (e.g. as containers, describing algebraic structure, describing multi-compositional systems, etc.). It can be hard to appreciate just how often they pop up without having seen the different lights in which they can be seen. In this sense, monads as monoids is just one perspective (and probably not the most enlightening).

Finally, while monads themselves are inarguably very useful in pure functional programming generally, I'm not sure the perspective as monads as monoids is helpful per se. I think the Kleisli perspective, which happens to be equivalent, is the most enlightening perspective here.

In summary, this response may be a little disappointing: I don't think that understanding this relationship is all that helpful or enlightening practically (i.e. for programming). However, it is a useful perspective to keep in mind, along with the others, when considering monads theoretically.

---
Tags: functional-programming, category-theory
---


# Question
Title: Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements?
I had a question about random shuffling. Given a sorted list, is it possible to design an algorithm to return a uniformly random arrangement of the items in a deque with the following operations:

* read from list and add to front of deque
* read from list and add to back of deque
* remove from front of deque and add to back
* remove from back of deque and add to front

I am trying to figure out an algorithm to do this without the aid of any other arrays or memory (i.e. outside of the original list of size N and the deque, there is no additional memory). After experimenting with it, I'm doubting it's possible to obtain a truly uniformly random arrangement of the items, but I'd love to be proven wrong. Any guidance would be appreciated.

# Answer
The final algorithm:

```
for each new element k:
    perform a random cyclic shift of the sequence on the deque
    insert k to the end of the deque
    perform an inverse cyclic shift

```

Now, why does it work? (There is probably a simpler way to put it; this is how I understand this)

We generate a random permutation $p$ (we would need additional memory for that, but I'll explain how to avoid it). We replace each input number $a\_i$ with pair $(a\_i, p\_i)$. Now it suffices to sort the pairs based on the second element. It works because different permutations correspond to different orders of elements after sorting.

To perform the sorting, we simply emulate insertion sort:

* Let $\[p\_1, \ldots, p\_m\]$ be the current numbers in deque, and they are in sorted order.
* Then another number $k$ arrives, such that $p\_1 \< \cdots \< p\_i \< k \< p\_{i+1} \< \cdots \< p\_m$.
* We perform the cyclic shift: $\[p\_{i+1}, \ldots, p\_m, p\_1, \ldots, p\_i\]$.
* We insert $k$ in the back: $\[p\_{i+1}, \ldots, p\_m, p\_1, \ldots, p\_i, k\]$
* We perform an inverse cyclic shift: $\[p\_1, \ldots, p\_i, k, p\_{i+1}, \ldots, p\_m\]$

To avoid storing the permutation, notice that it suffices to decide the relevant order of elements at the moment of insertion. I.e. for each element, you randomly determine its position among existing elements in the deque and perform the shifts as described.
> 1 votes

---
Tags: algorithms, queues
---


title: How do compilers assure stability?

text:
# Question
Title: How do compilers assure stability?
Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but that would require a c compiler to begin with. If a mistake is made in the making of one of the early iterations of compilers, it could propagate. How do compilers make sure that this doesn't happen? Obviously, no code is flawless, not even the processor is, but if you haven't somehow measured the stability, you don't even know if your compiler is stable. What assumptions are made and how is it justified? I would imagine it would be architecture-dependent too.

Edit: By stability, I mean that the code runs as intended.

# Answer
> 1 votes
The word that compiler writers use for this is "conformance". A compiler that correctly implements the language specification is conformant. There are companies who, as part of their business, sell conformance tests for various standards, including programming languages.

It's rare for errors to propagate through compiler generations by accident (although it has happened on purpose).

# Answer
> 4 votes
It happens that compilers contain subtle errors. No blatant errors, because blatant errors would be detected and fixed.

A compiler that is itself compiled by a compiler with subtle errors will tend to have blatant errors. They will be easy to detect because they are so blatant. They will be hard to fix because these blatant errors will be produced by perfectly fine source code, so whoever wants to fix it will have a hard time finding the real problem.

The solution will be to make a compiler of sufficient quality that bugs are very rare, and extremely rare within the compiler. We also expect compiler bugs to affect very complicated code more, so the compiler writer should write code that is simple and follows common coding patterns.

# Answer
> 3 votes
One answer is testing, testing, testing. E.g. GCC comes with an ever growing set of tests that are checked each time the compiler is built. Many compilers are required to pass the so-called triple test: Compile code for your compiler C using compiler A, giving C\_1; compile C with C\_1 giving C\_2, compile C with C\_2 giving C\_3. Now C\_2 and C\_3 were compiled with C, and should be equal. If not, something fishy is going on.

Take a look at Regher's "Embedded in Academia" blog, he is one of the people working around the LLVM compiler tools, and regularly touches on the tools and techniques used to make the compiler better (or automate parts of it's building).

# Answer
> 1 votes
In Computer Science this is covered by the use of T-Diagrams (or Tombstone Diagrams).

This explains how compilers are created for new languages and also how compilers can be ported from one platform to another. They also explain how flawed compilers can be fixed, but changing a compiler to fix a bug is much like changing a compiler to add a feature.

There are several sets of university class notes on this issue that Google reveals, which you could consult, but there is also a good question here (not a duplicate, but very useful):

Cross Compiler's T diagram

---
Tags: compilers, c, c++, error-estimation
---


# Question
Title: "Knapsack problem" with repetition, "lesser or equal" constraint, and recording all valid combinations
In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head.

Let $x\_i$, $ 1\leq i \leq n$ be the objects we are dealing with, and $p\_i$, $ 1\leq i \leq n$ the cost associated with each item. Suppose there exists some total budget $B$.

I now need to find **all** combinations of items, such that:

* the sum of their costs is lesser than or equal to the budget $B$
* each object $x\_j$ may appear any number of times, including not at all

This doesn't seem like a traditional optimization problem anymore, since I actually need to find all combinations that fulfill these constraints. How can this be solved efficiently? I was thinking about trying to modify the dynamic programming approach employed to solve the traditional knapsack problem, but it's a bit over my head.

# Answer
The number of solutions can easily be huge, so just writing out the solutions will take a long time. But this is *not* the knapsack problem, which gives you a budget (knapsack capacity) and values of the items, and ask for maximal value (or if some value is atainable).

One way to generate them all is to use backtracking: List all solutions that don't include object 1, then all that do include object 1 once, twice, ... Recursively check for solutions without/with object 2, ... I don't think there can be any more efficient way, and it does prune off combinations that are doomed (can't be extended).

Look if you can narrow the search somehow. Say order the objects so that you get promising combinations early, and cut off the search when you get enough of those.
> 1 votes

---
Tags: algorithms, combinatorics, knapsack-problems
---


# Question
Title: If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?
I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

> * If problem B is in P and A reduces to B, then problem A is in P.
> * Problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
> * Problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.

My questions are (if **I** then **II** then(?) **III/I**. If **III/I** and **III/II** then **IV**.)

* **I**: Are there a generalized form to reduces NP problem to either P or NP-complete?
* **II**: Are there a certain number of NP-complete problems?
* **III/I**: Are all of the NP-complete problems can be reduces to all other NP-problems?
* **III/II**: If we can reduce B in NP-complete problem to A in P, can we prove that all problem reduces to B is in P?
* **IV**: If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

# Answer
> 1 votes
I. I was not able to parse the question, sorry.

II. There is an infinite number of NP-complete problems.

III/I. Each NP-complete problem can be reduced to any other NP-complete problem.

III/II. If you show that there exists a (Karp) reduction from a NP-complete $B$ problem to a problem in P, then you have proved that all problems that reduce to $B$ are also in P. In particular this implies NP $\subseteq$ P, and hence P=NP.

IV. If a NP-complete problem is in P, then P=NP.

# Answer
> 1 votes
When it comes to polynomial time reductions from $A$ to $B$, I find it useful to think of it as "Solving problem $A$ by converting it to problem $B$, then using a 'Problem $B$ Solver'."

With this in mind:

1. There are currently many NP problems that have not (yet) been shown to be in NP-Complete or P. If there truly exists NP problems that are neither in NP-Complete nor P, then this would imply P!=NP. Moreover, Ladner's Theorem tells us that the converse is true: if P!=NP, then such *NP-intermediate* problems exist.
2. Yes, but it may not mean what you think it means. To answer this properly, we need to look at the definitions. NP problems are *decision* problems, and correspond to *languages*, which are collections of strings representing the instances that are in the language. But there are an infinite number of representations for a given problem. For example, the PRIME problem could be represented by the collection of binary strings whose value are prime. Alternatively, we could have stored them as the collection of strings in base 10. Or base 11. Or 12...
3. Yes: the definition of an NP-Complete problem is that every NP problem (incl. NP-Complete problems) can be reduced to it.
4. Yes: To solve an NP problem in polynomial time, reduce it to the NP-Complete problem then solve it in polynomial time.

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


# Question
Title: Does $20n$ belong to $O(n^{1-\epsilon})$ for some $\epsilon > 0$?
I am quite new to master theorem and I would like to ask the following question for $$()=4(/4)+20.$$ If there is a constant value like $20n$ does it affect the equation?

Would the equation look something like this for test case 1:

> Is $f(n) = 20n \in O(n^{log\_ba-\epsilon}) \in O(n^{\log\_4^4-\epsilon}) \in O(n^{1-\epsilon})$ for some $\epsilon \> 0$?

# Answer
Big O notation hides constant factors. In particular, for every constant $C \> 0$, $$ f \in O(g) \Longleftrightarrow Cf \in O(g). $$ In particular, for any $\epsilon \> 0$, $$ 20n \in O(n^{1-\epsilon}) \Longleftrightarrow n \in O(n^{1-\epsilon}). $$

This follows directly from the definition of big O. Indeed, suppose that $f \in O(g)$. Then there exist $N,A\>0$ such that $f(n) \leq Ag(n)$ for all $n \geq N$. This implies that $Cf(n) \leq ACg(n)$ for all $n \geq N$, and so $Cf = O(g)$. Similarly, if $Cf = O(g)$ then the same argument shows that $f = C^{-1} C f = O(g)$.
> 1 votes

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


# Question
Title: How to solve recursion with two separate converges rates
What is the correct way to solve the following recursion: $T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$

Or basically any recursion that has two parts which converge in a different rate.

I'm trying to get big $O$ approximation, as tight as possible, but I couldn't figure it out with any "traditional" approach.

# Answer
If you take the initial conditions $T(0) = 0$ and $T(1) = 1$ then you get A018819 (up to shift), which is essentially A000123. The asymptotics are known to be $T(n) = n^{\Theta(\log n)}$. The references under the second entry contain more accurate asymptotic information.

More explicitly, A018819 satisfies the recurrence $a(2m+1) = a(2m) = a(2m-1) + a(m)$, with $a(0) = a(1) = 1$. You can show inductively that $a(n) = T(n+1)$. Indeed:

* If $n = 2m+1$ then $$T(n+1) = T(2m+2) = T(m+1) + T(2m) = a(m) + a(2m-1) = a(2m) = a(2m+1) = a(n).$$
* If $n = 2m$ then $$T(n+1) = T(2m+1) = T(m+1) + T(2m-1) = a(m) + a(2m-2) = a(m) + a(2m-1) = a(2m) = a(n).$$
> 0 votes

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


# Question
Title: Context free languages invariant by "shuffling" right hand side
Given a grammar $G$ for a Context Free language $L$, we can augment it by "shuffling" the right hand side of each production, e.g.:

$A \to BCD$ is expanded to $A \to BCD \\; | \\; BDC \\; | \\; CBD \\; | CDB \\; | \\; DBC \\; | \\; DCB$

It may happen that the resulting language $L'$ generated by the expanded $G'$ is equal to $L$

For example:

```
Source               Shuffled
S -> XA | YB         S -> XA | AX | YB | BY
A -> YS | SY         A -> YS | SY
B -> XS | SX         B -> XS | SX
X -> 1               X -> 1
Y -> 0               Y -> 0

```

> Is there a name for such class of grammars ($L(G) = L(G\_{\text{shuffled}}))$?

> Furthermore, does this theorem hold?

**Theorem \[it doesn't hold, see Yuval's answer and comments\]:** If exists a grammar $G$ such that, $L(G) = L(G\_{\text{shuffled}})$, then for all $G'$ such that $L(G) = L(G')$ we have $L(G') = L(G'\_{\text{shuffled}})$

In other words the "shuffle invariance" of grammars also corresponds to a class of languages.

# Answer
Your theorem doesn't hold.

Consider the grammar

$$ \begin{align} &S \to 1T \mid T1 \\ &T \to 23 \mid 32 \\ \end{align} $$

Shuffling the grammar results in the same language.

Now consider instead the grammar $$ S \to 123 \mid 132 \mid 231 \mid 321 $$ which generates the same language.

Shuffling this grammar results in a larger language.
> 2 votes

---
Tags: context-free, reference-request
---


# Question
Title: Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular
> Prove that $L=\\{a^ncb^n| n \in \mathbb{N}\\}$ is not regular.

Here is my try, I would really appreciate if someone could tell me if this is a correct proof.

**Proof:** Lets assume L is regular. Then we know that L must meet the requirements of the pumping lemma. So let p the pumping number.

Let $w=a^pcb^p$. $w$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $|y|\>0,|xy|\leq p,xy^iz$ is in L $\forall i \in N$. Because $|xy|\leq p$ $y $ can only contain the symbol $a$(If $y$ would contain a symbol different from a it would imply that $|xy|\>p$, which is not possible). Therefore $y$ must be in the form $y=a^{p-k},0\leq k\<p$. So the word w equals $w=a^ka^{p-k}cb^p$, if we set i=2 we get $a^ka^{2p-2k}=a^{2p-k},k\<p$ and because $ a^{2p-k},k\<p\neq b^p$ it follows that the pumped $w$ is not in $L$. Which is a contradiction. Therefore $L$ is not regular.

$\tag\*{$\blacksquare$}$

# Answer
> 2 votes
**Proof:** Lets assume L is regular. Then we know that L must meet the requirements of the pumping lemma. So let p the pumping number.

Let $w=a^pcb^p$. $w$ is obviously of the length p and is in L. Therefore it should be possible to split w into three pieces xyz such that $|y|\>0,|xy|\leq p,xy^iz$ is in L $\forall i \in N$. Because $|xy|\leq p$ $y $ can only contain the symbol $a$(If $y$ would contain a symbol different from a it would imply that $|xy|\>p$, which is not possible). Therefore $y$ must be in the form $y=a^{p-k},0\leq k\<p$. So the word w equals $w=a^ka^{p-k}cb^p$, if we set i=2 we get $a^ka^{2p-2k}=a^{2p-k},0\<=k\<p$ and because $ a^{2p-k}\neq b^p$ it follows that the pumped $w$ is not in $L$. Which is a contradiction. Therefore $L$ is not regular.

$\tag\*{$\blacksquare$}$

# Answer
> 0 votes
Assume the language is regular, therefore has a finite state machine. Since the state machine is finite, there are n ≠ m such that $a^nc$ and $a^mc$ arrive in the same state. Therefore $a^nca^n$ and $a^mca^n$ arrive in the same state. But one is in the language, so that state must be accepting, and one is not in the language, so that same state must be non-accepting.

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


# Question
Title: Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant?
The standard Post Correspondence Problem concerns tiles with two rows of symbols, and whether a tile arrangement can be made so that the sequence of the top symbols of the tiles is equal to the bottom one.

Let $\text{n-PCP}, \text{n} \> 0$ a generalization of the Post Correspondence Problem where the tiles contain $\text{n}$ rows, and the sequences of the symbols have to be equal for all of these rows.

Obviously $\text{1-PCP}$ is decidable (in fact it's trivial because the answer to the problem is always true). $\text{2-PCP}$ is the standard PCP.

But what if $\text{n} \> 2$? Is it harder or can it be reduced to the standard PCP (like \>3-SAT being reduced to 3-SAT)?

# Answer
> 0 votes
$\text{n-PCP}$ can be reduced to $\text{2-PCP}$ as follows.

Let $M$ be a nondeterministic Turing machine that accepts an $\text{n-PCP}$ instance as input, guesses a solution for that instance, and then checks that it is correct. Clearly, $M$ accepts if and only if there is a solution to the input instance.

Now, let $p$ be an instance of $\text{n-PCP}$. The reduction encodes $M(p)$ as a $\text{2-PCP}$ instance in the standard fashion.

---
Tags: undecidability
---


# Question
Title: Is there a way to determine whether a list of integers can be a prefix function?
Say you had

(0,0,0,1,2,3,4,5,6,7,8,9,10)

or

(0,1,0,1,0,1,2,3,0,1,0,0,1)

Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a way to find whether a substring exists in a string using KMP, but is there a way to do it the other way around, starting at the apparent prefix function and ascertaining that it is indeed a possible prefix function, without knowing the string/substring itself at the start?

# Answer
> 2 votes
> Denote by $p$ the input prefix function. Refer to the characters of a word having $p$ as prefix function by their indexes $V=\\{0,1,2,...,\operatorname{length}(p)-1\\}$. We will keep a set of pairs $D$ of elements of $V$ to represent the characters that must be different. Finally, $V$ will be partitioned into equivalence classes according to the characters of the word that must be equal. I assume that to answer this question it is also given which is the alphabet $\Sigma$ of allowed letters to use. A possible variant of the question would give also a dictionary $L$ of allowed words.

**Algorithm**

* A non-zero as first entry tells you right away that the sequence is not a prefix function.
* Each positive value in $p$ tells you equality between certain pairs of characters of the potential word having that (presumptive) prefix function. Keep track of the equivalence classes that these equalities define, maybe with a disjoint set union data structure.
* If you ever find an increase by more than $1$ ($p\[k+1\]\>p\[k\]+1$) you can return immediately that it isn't a prefix function.
* Whenever, the sequence doesn't increase it will also tell you one pair of characters that must be different. Collect these pairs in $D$.
* Run by the pairs $D$ of vertices that must be different. If any belong to the same class return `false`.
* Finally, consider the graph $G$ with vertices given by the equivalence classes obtained above and where the edges are the elements of $D$. If only the alphabet $\Sigma$ is given, then we compute if the vertices of $G$ can be colored with the elements of $\Sigma$ such that adjacent vertices don't get the same color. In the variant in which the dictionary $L$ is given, then we check if any word in $L$ has the length of $p$ and its characters that are in positions being in the same equivalence classes are equal, and the characters forming a pair in $D$ are different. If these conditions are satisfied we output `true`. Otherwise we output `false`.

Let's do your examples.

**Example 1:** Given $p=(0,0,0,1,2,3,4,5,6,7,8,9,10)$, then $V=\\{0,1,2,...,12\\}$. That $p\[0\]=0$ tells us that we don't return `false` right from the beginning. That $p\[1\]=0$ tells us that characters $0$ and $1$ must be different. So, we insert $\\{(0,1)\\}$ in $D$. That $p\[2\]=0$ makes us insert $(0,2)$ in $D$. The rest of the entries of $p$ increase by $1$. So, we never return with a `false` caused by an increase larger than $1$. Moreover, there are no new insertions in $D$, but we do get the equivalence classes $\\{0,3,6,9,12\\},\\{1,4,7,10\\},\\{2,5,8,11\\}$. Since the two pairs in $D$, $(0,1)$ and $(0,2)$ don't consist of elements belonging the same equivalence class then we output `true`. Well, conditional of the variants of the problem in which the alphabet is small and the variant in which the dictionary of all words are given.

For example, the word $1231231231231$ has $p$ as prefix function. Well, if the alphabet has less than $2$ letters then we could give the example $1221221221221$. If the alphabet has only $1$ letter, we would need to output `false`.

**Example 2:** Given $p=(0,1,0,1,0,1,2,3,0,1,0,0,1)$, then $V=\\{0,1,2,...,12\\}$. That $p\[0\]=0$ makes us not return `false` from the beginning. That $p\[1\]=1$ tells use that $0$ and $1$ are in the same equivalence class. That $p\[2\]=0$ makes us insert $(0,2)$ in $D$. That $p\[3\]=1$ tells us that $0,1,3$ are in the same equivalence class. That $p\[4\]=0$ makes us insert $(0,4)$ in $D$. that $\[5\]=1$, tells us that $\\{0,1,3,5\\}$ are in a equivalence class. I guess you can continue. At the end the only equivalence class with more than $1$ element is $\\{0,1,3,5,6,9,12\\}$. The rest of the characters are on their own equivalence classes. In $D$ we have the pairs $(0,2),(0,4),(0,7),(0,8),(0,10),(0,11)$. None of these consist of characters from the same equivalence class. So, we return `true`.

For example, the word $0010200130450$ has $p$ as prefix function.

Let me add an example that returns `false` to have an example of that case.

**Example 3:** Given $p=(0,0,1,2,3,4,2,0)$, then $V=\\{0,1,2,...,6\\}$. Since $p\[0\]=0$ we don't return `false` from the beginning. That $p\[1\]=0$ makes us insert $(0,1)$ in $D$. That $p\[2\]=1$ tells us that $0,2$ are in the same equivalence class. That $p\[3\]=2$, tell us that $1,3$ are in the same equivalence class and that $0,2$, which we already knew are also equivalent. That $p\[4\]=3$ tells that $0,4$ are equivalent, $1,3$, which we knew, and $2,4$, which by now we knew too. That $p\[5\]=4$ tells that $1,3,5$ are equivalent. Now, that $p\[6\]=2$ tells us that $6$ and $1$ are equivalent. That's okay so far. But it also tells us that $0$ and $5$ are equivalent. Now, the problem with that is that that makes $1$ (which is equivalent to $5$) in the same equivalence class as $0$, but $(0,1)$ is a pair in $D$. So, we will have to return `false`.

---
Tags: algorithms, strings, substrings
---


# Question
Title: Relations between deciding languages and computing functions in advice machines
I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current understanding of the concepts. (I have a project in which I want to discuss Hava Siegelmann's analog recurrent neural nets, which recognize languages in P/Poly, but I'd like to understand and be able to explain to others implications this has for computing functions.)

Suppose I want to use an advice Turing machine $T\_1$ to calculate a function from binary strings to binary strings $f: \\{0,1\\}^\* \rightarrow \\{0,1\\}^\*$. $T\_1$ will be a machine that can compute $f$ in polynomial time given advice that is polynomial-size on the length of arguments $s$ to $f$, i.e. $f$ is in P/Poly. (Can I say this? I have seen P/Poly defined only for languages, but not for functions with arbitrary (natural number) values.)

Next suppose I want to treat $f$ as defining a language $L(f)$, by encoding its arguments and corresponding values into strings, where $L(f) = \\{\langle s,f(s)\rangle\\}$ and $\langle\cdot,\cdot\rangle$ encodes $s$ and $f(s)$ into a single string.

For an advice machine $T\_2$ that decides this language, the inputs are of length $n = |\langle s,f(s)\rangle|$, so the relevant advice for such an input will be the advice for $n$.

---

Question 1: If $T\_1$ can return the result $f(s)$ in polynomial time, must there be a machine $T\_2$ that decides $\\{\langle s,f(s)\rangle\\}$ in polynomial time? I think the answer is yes. $T\_2$ can extract $s$ from $\\{\langle s,f(s)\rangle\\}$, and then use $T\_1$ to calculate $f(s)$, and then encode $s$ with $f(s)$ and compare it with the original encoded string. Is that correct?

---

Question 2 (my real question): If we are given a machine $T\_2$ that can decide $\\{\langle s,f(s)\rangle\\}$ in polynomial time, must there be a way to embed $T\_2$ in a machine $T\_3$ so that $T\_3$ can return $f(s)$ in polynomial time?

I suppose that if $T\_2$ must include $T\_1$, then the answer is of course yes. $T\_3$ just uses the capabilities of $T\_1$ embedded in $T\_2$ to calculate $f(s)$. But what if $T\_2$ decides $L(f)$ some other way? Is that possible?

If we are given $s$, we know its length, but not the length of $f(s)$. So in order to use $T\_2$ to find $f(s)$, it seems there must be a sequential search through all strings $s\_f = \\{\langle s,r\rangle\\}$ for arbitrary $r$. (I'm assuming that $f(s)$ is unbounded, but that $f$ has a value for every $s$. So the search can take an arbitrary length of time, but $f(s)$ will ultimately be found.)

One thought I have is that the search for a string $s\_f$ that encodes $s$ with $f(s)$ has time complexity that depends on the length of the result $f(s)$ (plus $|s|$, but that would be swamped when $f(s)$ is long).

So now the time complexity does not have to do with the length of the input, but only the length of $f(s)$. Maybe $L(f)$ is in P/Poly if $f$ is in P? (Still confused here.)

Thinking about these questions in terms of Boolean circuits has not helped.

# Answer
I think the answer to Question 2 is "no", as far as we know. For instance, let $f$ be the function that parses its input $s$ as a 3CNF formula $\varphi$ and then returns the lexicographically earliest satisfying assignment to $\varphi$, or $\bot$ if none exists. Then it is easy to decide $L(f) = \\{\langle s,f(s) \rangle\\}$ in polynomial time, but (assuming P $\ne$ NP), you cannot compute $f$ in polynomial time (and assuming P/poly $\ne$ NP, advice doesn't help).

The following might be a better way to translate between functions and languages. Let $L'(f) = \\{\langle s,i,b \rangle : f(s)\_i=b\\}$, where $y\_i$ denotes the $i$th bit of $y$. (I assume that if $y$ has fewer than $i$ symbols, then $y\_i=\bot$.) Then if you can compute $f$ in polynomial time, you can decide $L'$ in polynomial time; and if you can decide $L'(f)$ in polynomial time and the length of $f(s)$ is polynomial in the length of $s$, then you can decide $L'(f)$ in polynomial time.
> 1 votes

---
Tags: complexity-theory, turing-machines, time-complexity, polynomial-time
---


# Question
Title: Finding a Good Estimate for Amount of Time Computers Spend Sorting Lists of What Lengths?
I have an assignment to envision and calculate the possible effects the implementation of a general sorting algorithm that is O(n) time and O(1) space ( assuming general case ) would have on computation and society.

In order to do that, I am trying to estimate how much computation time computers in server farms spend on sorting, and what general orders of magnitude the lengths of lists being sorted fall in. Server farms seem to be the most impactful area to analyze for pertinent effects, but if there are some other areas that people would expect to see an outsize effect, I would appreciate them being called out.

I can then present sets of assumptions with the "new" algorithm being faster at sorting lists at such a length and larger and how much faster than the current state of the art. eg. "If the new algorithm is even with the state of the art for lists of 500 billion items, and increases in time with "n" while the soa increases in time with "log n", and 1/2 trillion item and larger sorts take X% of server-farm computation, you could expect to see computation time for the same tasks reduced by order of magnitude Y%". Once I can get some firm numbers ( not the question here ) on how much electricity server farms use, then I can also electricity usage cost comparisons.

When I researched on the web, I found that an O(n)/O(1) sorting algorithm is considered theoretically possible, but undiscovered to this point. I suspect that there might not be much impact on computation, because there seems to be no incentives put out for someone to come up with such an algorithm ( or a proof that it cannot exist ).

What is a the fastest sorting algorithm for an array of integers? https://en.wikipedia.org/wiki/Sorting\_algorithm http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap09.htm#:~:text=We%20have%20now%20introduced%20several,quicksort%20achieves%20it%20on%20average

I have presumed that sorting algorithms in general use, at least for large lists like web search results, are O(n log n) time and O(1) space as a general matter of course. If this is in error, please point it out!

My apologies if this forum is not appropriate for this kind of question. In that case, I would ask for pointers on where I should go with this question.

Thank you.

# Answer
> 1 votes
There is no comparison based sorting algorithm faster than O(n log n). So this is all theory.

There are plenty of situations where sorting an array takes O(n) time. These are special cases, but happen a lot. For example a sorted array. Or a sorted array with few elements changed. And there are cases where sorting the whole array isn’t needed. Like if I see my address book on the screen, apparently sorted - but only the bits that I’m looking up are sorted.

Log n isn’t very large, so O(n) doesn’t mean it’s faster than say Quicksort for anything that is small enough to sort.

Server farms rarely sort. Databases are indexed, and indexes are updated, no sorting needed.

The effect on society would be zero. Some people would be able to handle their computational needs for slightly less money, that’s all the difference.

---
Tags: sorting, power-consumption
---