# Question
Title: Is {<M,w>|M prints more than 300 non-blanks on input w} decidable?
Let

$$ L\_{300}=\\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\\}.$$

Is $L\_{300}$ decidable?

My intuition is it is decidable because given $M$ and $w$, we need to check for a bounded number of steps which would be a function of the number of states in the finite automata of $M$, input alphabet and the length of the input $w$. Can someone give an intuition for getting the exact bound or tell if its undecidable ?

# Answer
> 1 votes
It is decidable. The decider $D$ is described as the following pseudocode by Church–Turing thesis. The syntax of the pseudocode is borrowed from Python.

```
configurations = [the initial confituration]
print_non_blank = []
min = 0
max = len(w) - 1
while M does not halt on w:
    simulate one step of M on w
    configuration = the current configuration
    if M prints a non-blank:
        print_non_blank.append(1)
        if sum(print_non_blank) > 300: # Check 1
            return ACCEPT

        # update the non-blank area
        p = the position where M prints the non-blank
        if p > max:
            max = p
        if p < min:
            min = p

    else:
        print_non_blank.append(0)

        # Check 2
        for i in reserved(range(len(configurations))):
            if print_non_blank[i]:
                break
            if configurations[i].head_position < min:
                if configurations[i].state == configuration.state and configuration.head_position < configurations[i].head_position:
                    return REJECT
            elif configurations[i].head_position > max:
                if configurations[i].state == configuration.state and configuration.head_position > configurations[i].head_position:
                    return REJECT
            else:
                break

    # Check 3
    for i in range(len(configurations)):
        if configurations[i] == configuration:
            if sum(print_non_blank[i:]) > 0:
                return ACCEPT
            else:
                return REJECT

return REJECT

```

The decider $D$ maintains an area of the tape (represented by the closed interval $\[$`min`$, $`max`$\]$) such that there are only blank symbols beyond the interval. We call this area *non-blank area*, and call the area represented by $(-\infty,$`min`$)\\,\cup\\,($`max`$, +\infty)$ *blank area*.

In addition to count how many non-blank symbols $M$ prints (Check 1), the decider $D$ performs two additional check. Check 2 checks for the pattern where the head of $M$ wanders in the blank area without printing any non-blank symbol, then reach a position with the same state that is no closer to the non-blank area. Check 3 checks for the case where the configuration is the same as some previous one. We can assert that $M$ will loop forever in both cases and infer whether it will print more than $300$ non-blank symbols accordingly.

Now all the rest work is to show that $D$ is indeed a decider, i.e. will always halt. We prove this by contradiction. Assume $D$ does not halt for some $M$ and $w$, then $M$ does not halt on $w$ too. Also, $M$ must print finite ($\le 300$) many non-blank symbols otherwise $D$ will detect it and halt no later than the time $M$ prints the $301$th non-blank symbol. As a result, the non-blank area is always a subset of a fixed area represented by, say $\[a, b\]$, during the running of $D$. We call the area represented by $\[a, b\]$ *universal non-blank area*, and call the area represented by $(-\infty,a)\cup(b,+\infty)$ *universal blank area*. There are two cases.

1. There are only finite many configurations where the head of $M$ is in the universal non-blank area. This means after some step, the head of $M$ will wander in the universal blank area forever (without printing any non-blank symbol, due to the definition of universal blank area), then there must be two configurations with the same state during the wandering. Also, the head of $M$ in the later configuration must be no closer to the non-blank area, otherwise the head will finally move into the non-blank area, which contradicts to the assumption that $M$ will wander in the universal blank area forever. As a result, this case is detected by Check 2 of $D$.
2. There are infinite many configurations where the head of $M$ is in the universal non-blank area. In this case, there must be two same configurations, so this case is detected by Check 3 of $D$.

Hence $D$ will halt anyway.

---
Tags: complexity-theory, turing-machines, computability, automata, undecidability
---


title: Lambda Calculus Generator

text:
# Question
Title: Lambda Calculus Generator
I don't know where else to ask this question, I hope this is a good place.

I'm just curious to know if its possible to make a lambda calculus generator; essentially, a loop that will, given infinite time, produce every possible lambda calculus function. (like in the form of a string).

Since lambda calculus is so simple, having only a few elements to its notation I thought it might be possible (though, not very useful) to produce all possible combinations of that notation elements, starting with the simplest combinations, and thereby produce every possible lambda calculus function.

Of course, I know almost nothing about lambda calculus so I have no idea if this is really possible.

Is it? If so, is it pretty straightforward like I've envisioned it, or is it technically possible, but so difficult that it is effectively impossible?

PS. I'm not talking about beta-reduced functions, I'm just talking about every valid notation of every lambda calculus function.

# Answer
Sure, this is a standard encoding exercise.

First of all, let $p : \mathbb N^2 \to \mathbb N$ any bijective computable function, called a pairing function. A standard choice is

$$ p(n,m) = \dfrac{(n+m)(n+m+1)}{2}+n $$

One can prove that this is a bijection, so given any natural $k$, we can compute $n,m$ such that $p(n,m)=k$.

To enumerate lambda terms, fix any enumeration for variables names: $x\_0,x\_1,x\_2,\ldots$.

Then, for each natural number $i$, print $lambda(i)$, defined recursively as follows:

* if $i$ is even, let $j=i/2$ and return variable $x\_j$
* if $i$ is odd, let $j=(i-1)/2$
    + if $j$ is even, let $k=j/2$ and find $n,m$ such that $p(n,m)=k$; compute $N=lambda(n), M=lambda(m)$; return application $(NM)$
    + if $j$ is odd, let $k=(j-1)/2$ and find $n,m$ such that $p(n,m)=k$; compute $M=lambda(m)$; return abstraction $(\lambda x\_n.\ M)$

This program is justified by the following "algebraic" bijection involving the set of all lambda terms $\Lambda$:

$$ \Lambda \simeq \mathbb N + (\Lambda^2 + \mathbb N \times \Lambda) $$

which is read as "the lambda terms, syntactically, are the disjoint union of 1) variables (represented as a natural), 2) applications (made by two lambda terms), and 3) abstraction (a pair variable/natural + lambda term)".

Given that, we recursively apply computable bijections $\mathbb N^2 \simeq \mathbb N$ (i.e. the function $p$) and $\mathbb N + \mathbb N \simeq \mathbb N$ (the standard even/odd one) to obtain the algorithm above.

This procedure is general, and will work on almost any language generated through a context-free grammar, which will provide a similar isomorphism to the one above.
> 24 votes

# Answer
As has been mentioned, this is just enumerating terms from a context free language, so definitely doable. But there's more interesting math behind it, going into the field of analytical combinatorics.

The paper Counting and generating terms in the binary lambda calculus contains a treatment of the enumeration problem, and a lot more. To make things simpler, they use something called the binary lambda calulus, which is just an encoding of lambda terms using De Bruijn indices, so you don't have to name variables.

That paper also contains concrete Haskell code implementing their generation algorithm. It's definitely effectively possible.

I happen to have written an implementation of their approach in Julia.
> 13 votes

# Answer
Yes. Take something that enumerates all possible ASCII strings. For each output, check if it is a valid lambda calculus syntax that defines a function; if not, skip it. (That check can be done.) That enumerates all lambda calculus functions.
> 12 votes

# Answer
Sure. We can directly generate them according to the definition of lambda terms.

In Haskell, we define the data type first,

```
data LC a  =  Var  a                -- Constructor <type> <type> ...
           |  App (LC a) (LC a)     --
           |  Lam  a     (LC a)     --  ... alternatives ...

instance Show a => Show (LC a)      -- `LC a` is in Show if `a` is in Show, and
  where
    show (Var i)    =  [c | c <- show i, c /= '\'']
    show (App m n)  =  "("  ++ show m       ++ " " ++ show n ++ ")"
    show (Lam v b)  =  "(^" ++ show (Var v) ++ "." ++ show b ++ ")"

```

and then with the use of a fair(er) `join`,

```
lambda :: [a] -> [LC a]
lambda vars  =  terms
  where
  terms  =  fjoin [ map Var vars ,
                    fjoin [ [App t s | t <- terms] | s <- terms ] ,
                    fjoin [ [Lam v s | v <- vars ] | s <- terms ] ]

  fjoin :: [[a]] -> [a]
  fjoin xs  =  go [] xs             -- fairer join
      where
      go [] []  =  []
      go a  b   =  reverse (concatMap (take 1) a) ++ go
                       (take 1 b ++ [t | (_:t) <- a]) (drop 1 b)

```

we just enumerate them, as e.g.

```
> take 20 $ lambda "xyz"
[x,y,(x x),z,(y x),(^x.x),(x y),(^y.x),((x x) x),(^x.y),(y y),(^z.x),(x (x x)),
 (^y.y),(z x),(^x.(x x)),((x x) y),(^z.y),(y (x x)),(^y.(x x))]

> take 5 $ drop 960 $ lambda "xyz"
[(((x x) y) (z x)),(^y.(^x.((x x) (x x)))),((^x.(x x)) (^x.(x x))),(^x.((^z.x)
 y)),((z x) ((x x) y))]

```

Look, the famous $\Omega = (\lambda x . xx)( \lambda x . xx )$ term is in there not that far down from the top!

`fjoin` is equivalent to Omega monad's `diagonal`.
> 8 votes

# Answer
I've come across one tool online that can generate sample strings from a regular expression: https://www.browserling.com/tools/text-from-regex. You can generate a lot of sample lambda terms by inputting something like this:

```
(\( (lambda \w\. )* \w+ \))*

```

Of course to get terms with arbitrary levels of nesting, you are going to need to use a context-free grammar, which is a more descriptive tool for defining a language than a regular expression. I haven't come across an existing tool for generating sample language sentences based on a context-free grammar definition, but there's no reason one couldn't be built.
> 0 votes

---
Tags: lambda-calculus
---


# Question
Title: How do you solve this [1,5,9,4] pair numbers problem?
So given an array of \[1,5,9,4\], find all pairs of numbers that can sum/subtract/divide/multiply to another number in the array(that number is not part of the pair), and return the total count of pairs satisfying this condition. (If a pair has 2 math operators that fit to the same number or if a pair can combine to 2 different numbers, dont count it twice).

How do I start this? and how do I explain my asymptotic complexity(Im a noob wit this)?

# Answer
This can be done in $O(n^2 \space log \space n)$.

1. Insert all N array elements with the indexes into a balanced BST.
2. For every $i \in \\{0,...N-1\\}$
3. For every $j \in \\{0,...N-1\\} \space and \space j \ne i$
4. Search for $(A\[i\]+A\[j\]),(A\[i\]-A\[j\]),(A\[i\]\*A\[j\]),(A\[i\]/A\[j\])$ in the BST and add $(A\[i\],A\[j\])$ if it is found in the BST and its corresponding BST entry $index \ne i\space and \space j$
Steps 1 and 2 runs for $O(n)$ time.
Step 2 runs for $n-1$ times = $O(n)$.
Step 3 runs for $4\*log\space n = O(log\space n)$.
Hence, time complexity is $O(n^2\space log \space n)$.
> 1 votes

---
Tags: algorithms, loops
---


# Question
Title: Best time complexity of sorting numbers in range [1...n log n]
given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them?

The answer is $O(n)$ but I don't understand this. of course counting sort itself is irrelevant, perhaps radix sort with base changing is the way to go, but I'm not sure of to change the base of $n\log n$.

# Answer
> 2 votes
Note in the RAM model, indirection always takes constant time regardless of how large the address is, so each process of radix sort with base $b$ takes $O(n+b)$ time. As a result, the radix sort takes $O((n+b)\log\_b(n\log n))=O((n+b)\log\_b n)$ time. Choosing $b=n$ makes the asymptotic time linear.

Edit: as suggested by Thinh D. Nguyen, since extracting each digit under base $b$ requires division and modular arithmetic, which are not supported by the standard RAM model, we may want to use the word RAM model instead.

# Answer
> 0 votes
*Theoretically*, there is no **linear sorting** algorithm if you consider only *nice* standard RAM model like (RAM model that was used to define recursive function and more recent model like Word RAM model).

Radix sort cannot help. Since pushing up the base to $b=n$ like in the answer of xskxzr, you need to extract the $b$-base digits.

In any theoretical RAM model, bitwise arithmetics are constant-time. Taking modulo an $O(\log(n))$-long number like $b=n$ is cumbersome.

*One last note*: if you still think that this can be done in linear time. That is OK, but it will never be a mathematical theorem. For otherwise, sorting with number in $\[1, n^{O(1)}\]$ can be done in linear time with radix sort from the very beginning of **every algorithm course** even in the $O(\log(n))$ word RAM model. But, **that is just wrong**. One cannot ignore the $polylog(n)$ overhead to simulate modular arithmetics. For students without sharp theoretical minds, that is acceptable.

*For an algorithm course, one can assume **unit-cost RAM**. That helps students to understand the big picture and neglect the details in time bounds analysis.*

---
Tags: algorithms, time-complexity, sorting, radix-sort
---


# Question
Title: Are there deterministic and/or non-interactive zero-knowledge proofs?
The Wikipedia page on zero-knowledge proof says

> Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the *soundness error*, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.

Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?

# Answer
> 3 votes
Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the *verifier* is deterministic then interactive proofs trivialize to RP, whereas if the *prover* is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.

Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies. See Wikipedia for many references.

# Answer
> 1 votes
At the very core of Zero Knowledge proof systems, lies the fact that proofs are published by asking the party to prove the correctness of its knowledge, via any one of many methods to verify a solution.
Since knowing the question in advance allows a party to forge another proof, the only way to get a reliable proof is via asking a random question out of a pre-determined set of questions, multiple times enough so that the chances of a cheat to pass through are practically impossible.
The *probabilistic behaviour* becomes inevitable from the fact that **any question asked at random can be predicted with a non-zero probability, since it comes from a pre-determined set of questions**. If the question to be asked was **not** from a set of pre-determined questions, current Zero Knowledge proofs would be deterministic.

# Answer
> 1 votes
Here's a deterministic zero-knowledge proof of sorts, if there are any logic gaps please let me know!: This zero knowledge proof involves proving you have a solution to three-colouring a map. The common zero knowledge proof for this scenario (Hats & Crayons for example)involves the Prover tries to convince the Verifier that you have found a solution by only showing pairs of countries chosen by the Verifier, then repeatedly recolouring the entire map to allow the Verifier to check another pair. After a huge number of checks, the Verifier is satisfied that it is highly unlikely that the Prover does not really have a genuine solution, and considers the proof good enough to have confidence in it.

However, here is a set up for an deterministic zero knowledge proof: You set out the huge blank uncoloured map on, say, a warehouse floor.

The Prover presents the Verifier with a set of cards and explains that each card has the label of a particular country of the map on one side and the other side is blue, red, or yellow. There are also three extra cards which are blank on the label side and have one of each colour on the flip side. The Verifier can examine the label side of the labelled cards to ensure there are no duplicates or country omissions, but is not allowed to check that all the cards have one of the three colours on the back (if the Verifier was allowed to do this, he would get some information about the overall proportion of the three colours: unlikely to be useful information, but knowledge all the same, zero knowledge is a requirement).

The Prover then places the cards on the corresponding countries label-side up and allows the Verifier to check that each card is placed on its correct country. The Prover also allows the Verifier to check the three extra cards have no labels, and contain the set of extra colours on their flip side.

The Prover then allows the Verifier to choose either 2 countries sharing a border (or 3 countries which each share a border with the other two).

Once chosen, the Prover takes the chosen 2 cards, adds one of the extra cards (if the Verifier has only chosen 2 countries, if not this step is skipped) taking care to add the extra card with the one colour not already present on the colour-side of the Verifier's chosen cards (he does not, of course, show the banker which colour he has added to the chosen 2). The Prover then thoroughly shuffles these three cards (which, remember are either two chosen by the Verifier plus an extra chosen by the Prover, or three chosen by the Verifier) and presents them to the Verifier colour-side up. The Verifier will always see three cards showing one of each of the colours. This proves to the Verifier that the 2 or 3 countries he picked do indeed have different colours (and these colours are from the allowed set of three colours).

Once checked, the Prover then shuffles the three cards again and places the labelled cards back on their countries (again, label side up). The Verifier is therefore satisfied that the Prover has reset the map as it was before.

This process repeats, enabling the Verifier to check that every single pair of connected countries have different coloured cards. With each verification cycle the Verifier will always only ever see three cards with the three allowed different colours, gaining no knowledge of what particular colour is on any particular country.

Not only is the Verifier able to check (very quickly) that there are no flaws in the solution, they also can see that the cards are not being changed with each verification cycle, so no room for the Prover to just be getting lucky each time.

As soon all the pairs (or trios) are checked once (the Verifier is allowed to check each pair more than once, does not need to), the Verifier is absolutely sure the solution is correct. But with each cycle, the Verifier has only ever seen the exact same answer: three different coloured cards (always showing the three chosen colours).

The Verifier has checked with absolute certainty that the solution is not flawed, but he has gained absolutely no useable knowledge about which colours go where, as he has only ever seen sets of the three chosen colours over and over again.

And to illustrate that the Verifier truly has zero knowledge after full verification of a true solution, if the Prover were to somehow be able to cheat by substituting colour cards during verification cycles, he would still only ever show the same three colours with each cycle.

The absence of re-setting the map takes away the possibility of the Prover just being lucky, while the addition of the blank extra cards does not allow the Verifier to gain any useful information, hence a non-probabilistic zero-knowledge proof.

# Answer
> -1 votes
In reality, there is no point in this distinction, because, even a conventional proof is probabilistic since there will always be a small probability that a cheating prover found the right solution by chance.

If fact, the only difference, is that in conventional methods, there is one good answer, the prover must prove he knows it, and must have a very small probability of success if it's not the case. However, in zero knowledge, the same proving protocol can be repeated any time you want with different data and for that reason, the probability of success of one iteration can be much larger, but if you repeat it a sufficiently large number of times, you will get the same level of security.

---
Tags: complexity-theory, interactive-proof-systems
---


# Question
Title: Does intersecting the output of 2 programs give the output of another program?
Let $S$ be the set of all programs that take integers as input and return integers as output and halt on all inputs. Does there exist a pair of program in $S$, call them $P\_1$ and $P\_2$, such that there exists no program $P\_3$ in $S$ for which the following hold for every integer $y$:

$P\_3(x)=y$ for some $x$ iff $P\_1(x\_1)=y=P\_2(x\_2)$ for some $x\_1$ and $x\_2 $.

# Answer
Let $f$ be a computable bijection from $\mathbb{N}^\*$ to $\mathbb{Z}$. For example, $f(1)=0,f(2)=1,f(3)=-1,f(4)=2,\ldots$

Note a non-empty subset of $\mathbb{Z}$ is the range of a program if and only if it is recursively enumerable. On the one hand, the range of a program $P$ can be enumerated by running $P(f(1)),P(f(2)),P(f(3)),\ldots$ On the other hand, for a non-empty recursively enumerable subset $X$ of $\mathbb{Z}$, there exists an enumerator $E$ that enumerates $X$. Suppose $E$ requires $n$ steps to output the first number, we can define a program $P$ that $P(i)$ returns the last number outputted by $E$ within at most $\max\\{n,f^{-1}(i)\\}$ steps.

Since the intersection of two recursively enumerable sets is still recursively enumerable, your $P\_3$ exists if and only if the intersection is not empty.
> 1 votes

# Answer
I think as long as $(P1\ range) \cap (P2\ range)$ is non-empty, their will always be a function p3 in S that has $(P1\ range) \cap (P2\ range)$ as its range. (range is set of all output values for function)

Proof argument goes like this:

Given:

1. $(P1\ range) \cap (P2\ range)\not= \phi$
2. $S$ is the set of all programs that take integers as input and return integers as output this means: for any subset of integers $I\subseteq Z$, there exists a program $P \in S$ such that $P:Z\mapsto I$ (this is important inference from definition of S)

Since $(P1\ range) \cap (P2\ range)\subseteq Z$,

we conclude from 1 and 2 there exists $p3\in S$,

$p3:Z\mapsto (P1\ range) \cap (P2\ range)$

I hope this is clear
> 0 votes

# Answer
No, such a pair of programs does not exist. In other words, a $P\_3$ always exists.

On input $x$ just compute $P\_1(x)$ and $P\_2(x)$. Because both programs halt on all inputs (by their definition), these two computations will stop and provide two results. Then $P\_3$ just compares these two results and iff they are equal outputs the result.

Your "programs" are the recursive funtions, and these are known to be closed under intersection.
> 0 votes

---
Tags: computability
---


title: Group isomorphism to graph ismorphism

text:
# Question
Title: Group isomorphism to graph ismorphism
In reading some blogs about computational complexity (for example here)I assimilated the notion that deciding if two groups are isomorphic is easier than testing two graphs for isomorphism. For example, on the stated page it says that graph isomorphism is a more general problem than group isomorphism.

Hence I am posing the following

> Given a group $G$ can someone give a construction of a graph $\Gamma(G)$ of size polynomial in $|G|$ such that $$\Gamma(G) \cong \Gamma(H) \iff G \cong H$$ for groups $G$ and $H?$

# Answer
The reduction is described in a classic paper of Miller.
> 13 votes

# Answer
Not so fast. There is a big lurking ambiguity here:

**How do you input your group for computation?**

Unlike graphs, groups can be input be means that are far different in terms of input size and resulting complexity. The version cited in Miller is one of the least natural and for example you wont find that in a computer algebra system such as GAP, Magma, or Sage. So while it has a theoretical premise, it would be going too far to call that settling the problem.

---

1. Generators and Relations: Group isomorphism is undecidable (graph isomorphism is decidable).

If history is the winner then the first mention of the Group Isomorphism problem was by Max Dehn in 1905. He assumed groups would be input by generators and relations. Adyan and Rabin in the 1950's proved that problem is *undecideable*. This situation occurs even if the group is trivial. So it is not just a cardinality issue. The key problem is you can create groups $G$ where to decide if $G=1$ would be to solve a rewriting problem that is non-primitive recursive. Similar to Halting type problems, it can't be done.

**For groups input by generators and relations: group isomorphism is harder than graph isomorphism, in fact undecideable.**

2. Inputs used by software systems: group isomorphism of permutation and matrix groups is at least as hard as graph isomorphism (not the other way around).

This model of input assume groups are encoded in some natural way, say as permutations on a finite set, or as matrices over a ring or field. These are the methods introduced by Cannon and Neubuser in the first computer algebra systems in the 1960s which went on to be GAP and Magma. In this model you can embed the graph isomorphism problem into the group isomorphism problem. See for example work of Heinekin-Liebeck. It has since been carried out in other forms by others such as Sergeichuk. The key idea is to embed the adjacency matrix of a graph into the relations of a $p$-group.

**For groups input for software systems: group isomorphism is at least as hard as graph isomorphism.**

3. Theoretical Complexity inputs: For a black-box group input, the group isomorphism is not known to be in NP or co-NP (graph isomorphism is in both).

This is a model for groups suggested by Babai-Szemeredi which assumes nothing about the input except that it be provided with (unit cost) functions for the group operations multiply, invert, test equality, and a set of generators. In their paper "On the complexity of matrix group problems" they discuss this problem and conclude its in $\Sigma^2$. The key problem is you cannot even define a certificate of isomorphism (thus it is not in NP) because you only have generators of the groups. So to provide an actual isomorphism $f:G\to H$ isn't possible, $G$ and $H$ are exponentially larger and from the generators alone you cannot know if $f$ is a valid homomorphism. At minimum you would seem to need a presentation of the groups, and that is not easily obtained.

**For black-box groups: group isomorphism is at least as hard as graph isomorphism.**

4. Cayley table inputs.

Sometime in the 1970's Tarjan, Pultr-Hederlon, Miller and others observed that groups input by their entire multiplication table could also be treated as graphs. In this way group isomorphism does reduce to graph isomorphism in polynomial time. Miller went much further with this observing that numerous combinatorial structures do the same, Steiner triples for example. He also demonstrated that semigroup isomorphism is equivalent to graph isomorphism.

Recently Babai proved that Graph Isomorphism is in quasi polynomial time and the reductions now estimate a complexity of about $n^{O(\log n)}$, which is precisely the best known bound for group isomorphism for groups given by Cayley table. While no one has shown these two problems to be polynomial time equivalent, the presenting timings suggest a closer relationship than expected.

**For Cayley tables: group isomorphism reduces to graph isomorphism.**

---

Which input is the "right" group input? Well the Kolmogorov complexity of finite group of order $n$ is $O((\log n)^3)$ which is roughly the input sizes of the methods 1-3 above. Those input methods are natural and easily created, say by calculating generating permutations of a Rubiks cube or looking at generating loops of a fundamental group. So it makes sense that much of the theory and practice of group isomorphism use those models.

**Yet** while no computational algebra system uses Cayley tables, and most theoretical computer science uses structures like permutation groups, matrix groups, and black-box groups, there is still a good defense for the Cayley table perspective. In general the Kolmogorov complexity of structures such as semigroups is of order $n$ is $O(n^2 \log n)$ -- a theorem of Marshall Hall. And so you could not input semigroups any more concisely than by multiplication table. Therefore when you want to compare the complexity of group isomorphism to other natural structures (quasi-groups, loops, semigroups, etc) it makes sense to agree on a common input model.
> 4 votes

---
Tags: complexity-theory, graph-isomorphism, group-theory
---


# Question
Title: Digraph vertices: classification by counting outgoing walks
I'm reproducing a question I posted on MSE (yet with no answer both there and by myself).

Given a (finite) directed graph $G = (V, E)$. For each vertex $v \in V$ and a natural number $n$, let $W\_v(n)$ be the number of walks in $G$ of length exactly $n$ originating at $v$. That is, $$W\_v(0) = 1 \quad\text{and}\quad W\_v(n + 1) = \sum\_{\substack{u \in V \\ (v, u) \in E}} W\_u(n).$$ Now, for $u, v \in V$, let $u \sim v$ iff $W\_u(n) = W\_v(n)$ for all $n$. This equivalence of vertices induces a partitioning of $V$. What is known on the complexity of computing this partition?

(By "computing", it may have meant an algorithm that assigns each vertex $v\in V$ a number of its class, so that two vertices are equivalent iff they get assigned the same number. I do see some resemblance to the Hopcroft's DFA minimization algorithm, but still the problem being solved is different... and I see this to be a corner case of some harder problems.)

# Answer
Let $A$ be the adjacency matrix of the graph, let $\mathbf 1$ be the all-ones vector, and let $\delta\_v$ be the indicator of vertex $v$. Then $$ W\_v(t) = \delta\_v A^t \mathbf 1. $$ It follows that $v \sim u$ iff for all $t$, $$ (\delta\_u - \delta\_v) A^t \mathbf 1 = 0. $$ Let $n = |V|$. The Cayley–Hamilton theorem shows $A^t$ is always a linear combination of $A^0,\ldots,A^{n-1}$. Therefore $$ v \sim u \Longleftrightarrow (\delta\_u - \delta\_v) A^0 \mathbf{1} = \cdots = (\delta\_u - \delta\_v) A^{n-1} \mathbf{1} = 0. $$ The latter property can be checked in polynomial time, so the partition can be computed in polynomial time. This procedure can be optimized by computing the kernel of the matrix $$ \begin{bmatrix} A^0 \mathbf{1} \\ \cdots \\ A^{n-1} \mathbf{1} \end{bmatrix} $$ and then finding all $\delta\_u-\delta\_v$ that belong to it.
> 3 votes

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


# Question
Title: Common name for a group of commands which break the linear structure of the program
I'm looking for a name of a group of all commands which are break the linear structure of the program.

In `C` PL, they are: `goto,return,break,continue`. `C++` also contains `throw`.

`Perl` has `last,next,return`.

Is there a common name for those groups of commands? Where can I read about those kind of commands?

# Answer
> 6 votes
These are control flow statements. There is a quite a large list of them on their Wikipedia page.

---
Tags: programming-languages
---


# Question
Title: Proving time complexity of $T(n) = 2T(n/3 + 1) + n$
I am working on proving the time complexity for the following problem, but believe I am stuck:

$$T(n) = 2T(n/3 + 1) + n$$

I have checked out this link here on time complexity on cs.stackexchange

However, I still cannot seem to find the answer. Using this proof from a Dartmouth course:

$a = 2, b = 3, c = 1$

In this case, I know logb a is .63, which is less than 1, so the complexity is $Θ(n)$. However, I don't know how to *prove that*.

I am trying to practice with the methods that I "know" - Master Theorem, Substitution, Iteration, or a Recursion Tree. And using one of those 4 methods, I can't find a way to prove the complexity is $Θ(n)$, even though I know that's the answer.

Would anyone be able to assist?

# Answer
> 2 votes
You can use the Akra–Bazzi theorem, a generalization of the master theorem.

Using the notations in the Wikipedia page:

* $g(x) = x$
* $k = 1$
* $a\_i = 2$
* $b\_i = 1/3$
* $h\_1(x) = 1$ (in fact, probably $h\_1(x)$ is a bit different, since $n/3+1$ isn't always an integer)
* $x\_0$ is a constant which is missing from your recurrence relation

You can easily check that all conditions of the theorem hold. To get the asymptotics, we first compute the value of $p$, which is the solution to $2(1/3)^p = 1$, that is, $p = \log\_3 2$. Next, we calculate the integral appearing in the answer formula: $$ \int\_1^x \frac{u}{u^{p+1}} \\, du = \int\_1^x u^{-p} \\, du = \frac{x^{1-p}-1}{1-p}. $$ We conclude that $$ T(x) = \Theta\left(x^p\left(1 + \frac{x^{1-p}-1}{1-p}\right)\right) = \Theta(x^p + x) = \Theta(x^{\max(p,1)}). $$ Since $p \< 1$, the answer is $T(x) = \Theta(x)$.

More generally, the Akra–Bazzi theorem shows that the master theorem applies even when the applications of $T$ on the right-hand side of the recurrence are off by a small amount (at most $O(x/\log^2 x)$).

# Answer
> 1 votes
You could try to show by induction that T(n) ≤ 5n. We have T(n) = 2 T (n/3 + 1) + n ≤ 10(n/3 + 1) + n = 4 1/3 n + 10 ≤ 5n if n ≥ 15, so if you show T(k) ≤ 5k for some range n/3 ≤ k \< n, n ≥ 15, the problem is solved.

---
Tags: algorithm-analysis, time-complexity, runtime-analysis, master-theorem
---


# Question
Title: How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?
Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there exists another set that covers strictly more elements than $S$ does. Is this problem still NP-complete?

To be clearer, let's think about the Set Cover problem as an optimization problem: what is the maximum number of elements that can be covered by $k$ sets. The decision version is: are there $k$ sets that cover at least $m$ elements? (where $m$ is part of the input, and the version you were saying is simply the special case when $m=n$). Now the problem is, for $k$ given sets (as part of the input), does there exist $k$ other sets that cover strictly more elements than the $k$ given sets do.

# Answer
> 2 votes
Here is a reduction from Set Cover to your problem. Let $(\\{S\_1,\ldots,S\_m\\},k)$ be an instance of Set Cover, and let $U = S\_1 \cup \cdots \cup S\_m$. Let $x\_1,\ldots,x\_k$ be $k$ new elements, and consider the following instance of your problem:

* The sets are $S\_i \cup \\{x\_j\\}$ for $i \in \[m\]$ and $j \in \[k\]$, together with the set $U$.
* The given cover consists of $S\_1 \cup \\{x\_j\\}$ for $j \in \[k-1\]$ together with $U$.

The given cover covers all elements but $x\_k$. There is a cover which covers more elements – that is, all elements – iff $U$ can be covered by at most $k$ sets from $S\_1,\ldots,S\_m$.

---
Tags: optimization, np-complete, decision-problem, set-cover
---


# Question
Title: Matching elements of two lists to identify the missing ones
Given two arrays of integers, A and B, with same size (or two bit vectors A and B with some bits enabled)

What would be the faster way to create a list C containing the elements from B not in A, (or the indexes of the bit vector B not enabled in A)?

# Answer
> 3 votes
The two questions are rather different. If $A$ and $B$ are given as unsorted lists, then one thing you could do is to sort $A$ and $B$ together, putting elements of $A$ before those of $B$ in case of ties, and then do a simple linear scan. This runs in $O(n\log n)$ time, where $n$ is the length of both arrays.

If the arrays are sorted then you can just merge them, in $O(n)$, and continue as before.

If the "arrays" (really sets) are given as bit-vectors, then you can use bitwise operations; details left to you.

---
Tags: algorithms
---


# Question
Title: Should I keep a relevant constant in the Time Complexity?
I designed an algorithm, and the Time Analysis provided next time complexity:

$\mathcal{O}(2^p \cdot (\frac{t}{2}/2^p) \cdot \frac{n}{4})$

what must be simplified to:

$\mathcal{O}(2^p \cdot \frac{n^2}{16})$ = $\mathcal{O}(2^p \cdot n^2)$

That constant factor is quite relevant in this case, and the only reason I'm considering keeping it, is because represents an important fact of the algorithm behavior.

# Answer
In asymptotic notation constant factors are "modded out". For example, an algorithm runs in time $O(n)$ iff it runs in time $O(2n)$ iff it runs in time $O(n/2)$.

If you want to capture such a difference meaningfully, you have (at least) two options:

1. **Add another parameter.** There could be a parameter $t$ such that your algorithm runs in time $O(tn)$. One way to think about it is that the algorithm runs in time $O\_t(n)$, i.e., with a big O constant that depends on $t$, and the dependence on the big O constant on $t$ is $O(t)$.
2. **Count a specific operation.** In some cases you might be able to count a specific type of operation more accurately. For example, perhaps one sorting algorithm performs $(2 \pm o(1)) n\log n$ comparisons on average, and another performs $(3 \pm o(1)) n\log n$ comparisons on average.
> 3 votes

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: Optimal assignment of +-1 values to vertices in a graph
Let $(V, E)$ be a simple connected undirected graph, $f: V \to \\{-1, +1\\}$, and $g: E \to \\{-1, +1\\}$. The function $g$ is completely defined by $f$, while $f$ is something we get to choose. The only thing we know about $g$ is that negating $f(v)$ causes $g(e)$ to negate whenever the edge $e$ is adjacent to vertex $v$, and that there are no other changes to $g$. The problem now is to choose $f$ to maximize $\sum\_{e \in E} g(e)$. Is there are an efficient algorithm to solve this problem?

You may assume that the graph is of some specific form which includes trees as a proper subset. If the graph is a tree, then it is easy to come up with an efficient algorithm for this problem, starting from the root and moving towards leaves.

# Answer
This is the maximum cut problem.

The function $g$ can be given explicitly as $g(\\{u, v\\}) = H\_{\\{u, v\\}} f(u) f(v)$ for some $H \in \mathbb{R}^{E}$. Each choice of $f$ divides the vertices into two sets $V\_+ = \\{x \in V : f(x) = +1\\}$ and $V\_- = \\{x \in V : f(x) = -1\\}$. The set of edges connecting $V\_+$ and $V\_-$ is the cut-set $C = \\{\\{v\_+, v\_-\\} \in E: v\_+ \in V\_+ \text{ and } v\_- \in V\_-\\}$. The term to maximize is

$\sum\_{e \in E} g(e) = \sum\_{e \in C} g(e) + \sum\_{e \in E \setminus C} g(e) = \sum\_{e \in E} H\_e + 2 \sum\_{e \in C} (-H\_e)$

This is maximized by a maximum cut $C$ under edge-weight $-H\_e$ for each edge $e$.

When there are both negative and positive weights, it is known that max-cut is NP-hard in general (min-cut is equivalent to max-cut with weights negated). In contrast, max-cut (min-cut) problem with non-positive (non-negative) weights has an efficient general algorithm.

Using knowledge of the structure of the graph may provide an efficient algorithm. It is easy to come up with an $O(n)$ algorithm when the graph is a tree, where $n$ is the number of vertices. For planar graphs, there are algorithms which solve max-cut in $O(n^{3/2} \log(n))$ time.

Useful search terms include submodular function and Ising spin glass model.
> 2 votes

---
Tags: graphs, optimization
---


# Question
Title: Prove that it is undecidable whether a given LBA accepts a regular set
I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than Turing machines. Or should I approach with reductions using computational histories of a Turing machine on an input.

# Answer
> 1 votes
Thanks to @YuvalFilmus I managed to reduce the **Halting problem** to the given problem. We design an LBA B, that given an instance of the Halting problem, $\langle M,x\rangle$, accepts the valid computation histories of M on x. If M doesn't halt on x, $L(B)=\phi$ which is regular. However, if M does halt $L(B)=VAL-COMPS(M,x)$ which is not regular(not even CFL). Techinically, I have reduced the complement of the Halting problem, but as we know that it is also not decidable, so it's fine.

---
Tags: complexity-theory, turing-machines, undecidability, linear-bounded-automata
---


# Question
Title: Karp hardness of an equidistant vertex set
What is the hardness of the following problem?

> **Input**: An undirected graph $G(V, E)$ and a natural number $k$
>
> **Output**: **YES** if $G$ has an equidistant vertex set of size $k$, otherwise **NO**

$\DeclareMathOperator{\dist}{dist}$An **equidistant vertex set** is a set of vertices $V'\subseteq V$ such that for every two pairs of vertices $u, v\in V'$ and $w, s\in V'$, we have $\dist(u, v) = \dist(w, s)$, where $\dist(u, v)$ is the length of a shortest path between $u$, $v$.

# Answer
Your problem is NP-hard, by reduction from E3SAT, an NP-hard variant of 3SAT in which every clause involves 3 different variables.

Let $C\_1 \lor \cdots \lor C\_m$ be an instance of 3SAT; we can assume that $m$ is larger than some constant, since otherwise we can brute force the answer in constant time. We construct the following graph:

* Vertices: There is a vertex $(C\_i,\ell)$ for each clause $C\_i$ and for each literal $\ell$ appearing in the clause.
* Edges: We connect $(C\_i,\ell)$ and $(C\_j,\ell')$ if $i \neq j$ and $\ell \neq \lnot \ell'$.

Here are a few claims:

1. The formula is satisfiable iff the graph contains an $m$-clique. Indeed, if the formula is satisfiable, we choose one satisfied literal from each clause, and these are the vertices of the clique. In the other direction, an $m$-clique must identify a literal from each clause. These literals are non-contradictory, and so correspond to a (possibly partial) satisfying truth assignment.
2. The diameter of the graph is 2. Indeed, given two vertices $(C\_i,\ell),(C\_j,\ell')$ (where possibly $i=j$), assuming $m \geq 3$ we can find a vertex $(C\_k,\ell'')$ such that $k \neq i,j$ and $\ell''$ involves a different variable from $\ell,\ell'$.
3. If $(C\_i,\ell)$ and $(C\_j,\ell')$ are at distance exactly 2 then either $i = j$ or $\ell = \lnot \ell'$.
4. Suppose that $K$ is a "2-clique", that is, a set of vertices in which any two vertices are at distance exactly 2. Pick some $(C\_i,\ell) \in K$. If all vertices in $K$ are of the form $(C\_i,\cdot)$ then $|K| \leq 3$. Otherwise, let $(C\_j, \lnot \ell) \in K$, where $j \neq i$. Every other vertex $(C\_k, \ell') \in K$ must satisfy $k \neq i$ or $k \neq j$; suppose, without loss of generality, that $k \neq i$. Then $\ell' = \lnot \ell$. Since $(C\_k, \lnot \ell)$ and $(C\_j, \lnot \ell)$ are at distance 2, necessarily $j = k$. That is, in this case $|K| \leq 2$.
5. Therefore if $m \geq 4$, there is an equidistant vertex set of size $m$ iff the formula is satisfiable.
> 4 votes

---
Tags: np-complete, np-hard, np
---


title: Relating a proof to a Haskell program

text:
# Question
Title: Relating a proof to a Haskell program
I am trying to relate the following integer square root theorem

$\forall x: \mathbb{N}, \exists y : \mathbb{N}((y^2 \leq x) \land (x \< (y+1)^2))$

and its proof to its role as a specification of the Integer Square Root `isqrt` ($\lfloor \sqrt{x} \rfloor$) function in a Haskell program.

Below is a inductive proof of the theorem and the related Haskell program. The proof was done using natural deduction in the Fitch system, hence there are notational differences between code and proof e.g. no $\leq$ in Fitch.

For my question the details of the proof are not important. I wish to focus on the base case, and the two cases involving $\exists$-Elimination and $\lor$-Elimination.

I used Quickcheck as a reasonable check that the theorem holds in the code.

I can see that cases **1** and **2** in the proof correspond to the guard conditions in the Haskell definition of `isqrt` function. I did not specify, prove, and implement the function `isqrt` in any structured way. I just used any examples I could find. I believe that there must some more formal transformation from proof to code that I am missing. So despite having written both the proof and code the precise correspondence between both eludes my comprehension.

Is there a technical name for this form of proof to program relation? I would be grateful for an explanation or pointer to the literature.

```
module Peano where
import Test.QuickCheck

data Nat = Z | S Nat deriving Show
-- addition
(+@) :: Nat -> Nat -> Nat
Z +@ y = y
(S x) +@ y = S (x +@ y)
-- multiplication
(*@) :: Nat -> Nat -> Nat
x *@ Z = Z
x *@ S y = (x *@ y) +@ x
-- square
sqr x = x *@ x
-- equality
(=@) :: Nat -> Nat -> Bool
Z =@ Z  = True
(S m) =@  (S n) = m =@ n
_=@ _  = False

-- lesst than
(<@) :: Nat -> Nat -> Bool
Z <@ Z = False
Z <@ x | not(x =@ Z) = True
x <@ Z | not(x =@ Z) = False
(S x) <@ (S y) = x <@ y

-- less than or equal
(<=@) :: Nat -> Nat -> Bool
x <=@ y = if (x =@ y) || (x <@ y) then True else False

-- Integer square root function
isqrt Z = Z
isqrt (S x) | (sqr (S (isqrt x))) <=@  (S x) = (S (isqrt x))
            | (S x) <@ (sqr (S (isqrt x))) = isqrt x

-- test with Quickcheck
instance Arbitrary Nat where
 arbitrary = oneof [return Z, (S  <$>  arbitrary) ]

isqrtPostCondition :: Nat  -> Bool
isqrtPostCondition x  = (sqr (isqrt x) <=@ x) && (x <@ sqr(S (isqrt x)))
check = quickCheck isqrtPostCondition
-- +++ OK, passed 100 tests.

```

# Answer
Your goal is to “prove” --I'm using bullets “•” for syntactic separators-- $$ ∀x \\;•\\;\\; ∃y \\;•\\;\\; y² ≤ x \< (y+1)²$$

---

### Proof Methods

In the natural deduction style, one proves “∀ x : ℕ • P x” by proving two statements:

```
Base case      :: P 0
Inductive step :: P a ⇒ P (S a) , for a : ℕ and S successor function

```

Where, in this case, $$P x \\;\\;≡\\;\\; ∃y \\;•\\; y² ≤ x \< (y+1)²$$

In the constructive fashion, one proves “∃ y • Q x” by *actually finding* such a $y$ using whatever data is available.

### Base case

For the \[base\] case the input `x` is `0`, and we need to *find* some $y$ with $y² ≤ x \< (y+1)²$. Clearly $y = 0$ works as shown in the proof your posted.

### Inductive step

For the \[inductive\] case where the input `x` is of the shape `S a`, we need to *find* a $y$ with $y² ≤ S a \< (y+1)²$, (\*).

1. However, we have the assumption $P a$ which gives us a $b$ with $b² ≤ a \< (b+1)²$ --which looks really close to the goal (\*).
2. To reach our goal (\*), let's do the simplest thing possible: replace $a$ with $S a$ in (1) thereby obtaining $b² ≤ S a \< (b + 1)²$. Because of (1), and the transitivity of ≤, the left part is true and the whole thing reduces to: $$S a \< (b + 1)²$$
3. So if this is true, then we are done and the answer is $b$.
4. If it is not true, then we must have it complement: $$(b + 1)² ≤ S a$$

* But from (1) we also have $a \< (b + 1)² = b² + 2b + 1$ thus we obtain $S a = a + 1 \< (b² + 2b + 1) + 1 ≤ b² + 4b + 2 = ((b + 1) + 1)²$
    * Hence, we have found that $(b + 1)² ≤ S a \< ((b + 1) + 1)²$ and so we may take the output $y$ to be $b + 1$ for our goal (\*).

---

# Curry-Howard: Proving ≅ Programming

The above was a proof \[sketch\] which corresponds to the a program.

A proof of $$∀ x : ℕ • ∃ y : ℕ • R(x, y)$$ corresponds to the program

```
-- Output y = prog x satisfies relationship R(x, y), for all input x.
prog :: Int → Int
prog 0  = “the y found in the base case of the proof”
prog n  = “the y found in the inductive step,
             along with any conditionals and recursive calls”

```

Applying this to our above proof yields,

```
prog :: Int → Int
prog 0 = 0
prog n = let a = n - 1 ; b = prog a
         in
           if   a + 1 <= (b + 1) * (b + 1)
           then b
           else b + 1

```

Hope that helps :-)
> 5 votes

---
Tags: proof-techniques, correctness-proof, formal-methods, haskell
---


# Question
Title: Simple question on the phrasing on a PBS Infinite Series video
What does she mean by finding the 6 qubit quantum state $|010001\rangle$ from a sphere of dimension $2^6$.

Here is the link: https://www.youtube.com/watch?v=IrbJYsep45E at time 8:47.

# Answer
The state of an $n$-qubit system is a superposition of the $2^n$ pure states $$ \sum\_{x \in \\{0,1\\}^n} \alpha\_x \left| x \right\rangle, $$ where the $\alpha\_x$ are complex numbers satisfying $\sum\_x |\alpha\_x|^2 = 1$. The $2^n$-dimensional (complex) *sphere* is just $$ \\{ (\alpha\_{0\dots0},\ldots,\alpha\_{1\dots1}) \in \mathbb{C}^{2^n} : \sum\_x |\alpha\_x|^2 = 1 \\}. $$ I'm not sure what "finding" $\left|010001\right\rangle$ on the sphere means, though.
> 1 votes

---
Tags: quantum-computing
---


# Question
Title: Are all finitely recursive context free languages parseable with a regexp?
Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown automata.

Now, let's put an additional constraint on the language: the maximum recursion amount must be finite.

Because the stack size has an upper bound in this case, my understanding is that there are finite number of stack configurations reachable. This means I could number them 0, 1, 2, 3, ..., N. So, I should be able to create a deterministic finite automaton (DFA) with states 0, 1, 2, 3, ..., N that recognises the same language that the pushdown automaton recognises.

Now, if I'm able to create an equivalent DFA, doesn't it mean that there exists a regular expression that can parse the context-free language with maximum recursion amount?

So, my theory is that all context-free languages that have a maximum recursion amount can be parsed with regular expressions. Is this theory correct? Of course, the theory says nothing about the complexity of the regular expression, it just says such a regular expression should exist.

So, in other words: if your stack memory is limited, a regexp can do the job of a HTML/XML parser!

In principle, isn't it true that computers with finite memory are actually DFAs and not Turning machines?

# Answer
We can take it even further: if we put a limit on the size of the HTML/XML, say 1PB, then there is only a finite number of them, so we can trivially parse them in $O(1)$ using a giant look-up table. However, that doesn't seem to tell us much about the complexity of parsing HTML/XML in practice.

The issue at stake here is *modeling*. A good model abstracts away the salient points of a real world situation in a way that makes the situation amenable to mathematical inquiry. Modeling HTML/XMLs as instances of arbitrarily recursing language forms a better model in practice than your suggestion or my suggestion.
> 6 votes

# Answer
**Yes.** If you have a PDA which never makes the stack longer than $n$, then there are a finite number of stack contents. Thus the number of (PDA state, stack contents) values is also finite. Thus it's possible to build a finite automaton with that many states to recognize the same language as the PDA does. From a finite automaton it's possible the build an FDA, and from an FDA it's possible to build a regular expression for the same language.

It's not practical though, the resulting regexp will probably be very long (much longer than $O(2^n)$).
> 2 votes

# Answer
This is true: a computer is, in theory, a finite-state machine. So it can only recognise regular expressions.

But suppose the computer isn't yet fully-built. Now, we can implement the full push-down automaton. When the PDA reaches the limit of the stack as currently built, it just waits until the next bit of the stack is bolted on. That's totally within the mathematical model of a PDA; nothing in the model says that the automaton can't take coffee breaks.

PDAs don't actually recognise infinite strings; they recognise finite strings of unbounded length. Every one of those strings will be recognised using a finite stack. So we never need to wait an infinite amount of time for the stack to be built out to the required depth.

Now you might have a theory about the maximum size of the universe. If that's true, then there is necessarily a limit to the length of the input to the PDA, and then it could have used a regular language instead. But your theory might be wrong, or it might be invalidated by some future event. We won't really know until we get there. Meanwhile, our arbitrarily expandable PDA can continue recognising the arbitrarily-long input until the end of the input is reached, at which point it will render judgement.
> 1 votes

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


title: Travelling Problem with Constraints

text:
# Question
Title: Travelling Problem with Constraints
Consider a network with $N$ nodes $1,...,n$. Every node is connected to every node via a weighted edge, where the weight represents distance.

You start your travel at a given node, say $1$, and end your travel at a given node, say $12$. Your travel has $T$ time steps. At time step $t=1$ you must visit one of nodes $\\{1,7,4\\}$, at time step $t=2$ you must visit one of the nodes $\\{7,3,45,9\\}$, and so on. In other words, at a given time step, you are given a set with at minimum $1$ and at maximum $K\leq N$ nodes. Choose the nodes for all time steps such that the cumulative distance is minimized.

Am I correct, that such problem is NP hard? Given $T$ time steps and that at most $K$ nodes are possible at each time step, the complexity would be $O(K^T)$, right?

What algorithms could be applicable or useful for such a problem? In my scenario, $T$ can be very large (up to 20,000) but $K$ is rather low (10 on average, at most 100).

(**Edit**) - I encountered the problem in a diary of a traveller. For example, you know that a traveller started his journey at some location. For every journey entry, besides the raw text, the writer in the title writes a date and a location name.

The problem is there often exist several different coordinates for a location name (i.e., multiple locations exists with the same name). An (I think reasonable) assumption I have come to, is that the shortest possible path (from start to finish) should approximate the travelled route quite well. I have a data set of multiple travellers with diaries like this and want to plot the routes onto a map (and hope to display a travelled route approximately in the way which in it was really travelled).

I have not yet come up with any good and general solution (besides brute-force computing the distance of every possible route, which may be impossible because there exist tons of diary entries and so many location names have multiple possible coordinates).

# Answer
> 0 votes
The problem can be solved efficiently: in $O(K^2 T \log (KT))$ time.

Build a graph where each vertex corresponds to a pair $(t,i)$, where $t$ is a time step and $i$ is one of the nodes that is allowed to be visited at time $t$. Add edges from $(t,i)$ to $(t+1,j)$ for every $t,i,j$, with a length that corresponds to the travel time from $i$ to $j$. Add a source node $s$ with edges from $s$ to each $(1,i)$ of length 0, and a sink node $t$ with edges from each $(T,i)$ to $t$ of length 0. Then, find the shortest path in this graph from $s$ to $T$.

The graph has $O(KT)$ vertices and $O(K^2T)$ edges, so Dijkstra's algorithm for finding shortest paths will run in $O(K^2 T \log (KT))$ time.

---
Tags: time-complexity, shortest-path, network-analysis
---


# Question
Title: Why checking if tuple belongs to join of two tables is NP-complete?
I have read that checking if tuple belongs to join of two tables is NP-complete.
I had computional-complexity activities during my studies, I remember basics, however I have forgotten details. Nevertheless I don't understand why it is NP-complete, it seems to me that I can solve it in polynomial time.

Let's consider specific example:
We have two tables, $T\_1$ and $T\_2$, where $|T\_1|=m$ and $|T\_2|=n$.
Now, let $t$ will be a tuple $t=(a,b,c)$. Then I can easily give polynomial algorithm for checking if join of $T\_1$ and $T\_2$ containg tuple $t$.

Is is sufficient to get $T\_1\times T\_2$ and in linear time check if this tuple is contained in result. Please note that size of $|T\_1\times T\_2|=n\times m$ is polynomial.

Where am I wrong?

# Answer
If the claim is:

> for instance, given a join query $Q$ and a relational database $D$, checking if $Q(D)$ returns a tuple is NP-complete as well

the NP-completness is about the decision if that join operation returns an empty set or not (for instance because the join condition is not satisfied by any pair of tuples).

So, if this hypothesis is true, the claim is not, as you are asserting, about the fact that a certain tuple belongs to the result or not (for instance this could be checked by verifying that the tuple satisfies the join condition).
> 3 votes

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


title: Help understanding ip address classes

text:
# Question
Title: Help understanding ip address classes
*microsoft.com* has the ip address ***23****.96.52.53*

Since the first number is $23$, this is *class A*.
Does this mean *microsoft* owns all the addresses from ***23****.0.0.0* to ***23****.255.255.255* ?

# Answer
> 6 votes
The original division and allocation of IP addresses used a system called classful IP addressing. This is the division to which you are referring, in which a class A network would receive all addresses X.0.0.0-X.255.255.255 and have over 16.5 million host addresses. As designated below, the network bits in classful addressing are divided in 8-bit groupings.

(source: intenseschool.com)

The modern internet utilizes an alternative subnetting system called classless inter-domain routing (CIDR) to more efficiently allocate and distribute IPv4 addresses. This technique is based on variable length subnet masking (VLSM) which allows one to set arbitrary-length prefixes and accordingly allow address space to be allocated on bit lengths other than the previous 8 bit boundaries. This allows one to specify the most significant (i.e. *network*) bits with CIDR notation by notating the prefix by the number of bits designating the network, yielding the host bits by omission. We'll use your example for specific demonstration.

Utilizing ARIN to search the address number, we can see that the IP block in question is not, in fact 23.0.0.0 - 23.255.255.255, but 23.96.0.0 - 23.103.255.255 with a CIDR notation of 23.96.0.0/13. "/13" indicates that the first 13 bits of the IP address are used to specify the network address space and accordingly the remaining 19 bits specify the host space.

We'll convert the Dotted Decimal Notation (DDN) to binary to show how the math works. Keep in mind, binary is base-2, meaning that each bit is an exponentially higher value of 2:

27 26 25 24 23 22 21 20

-or-

128 64 32 16 8 4 2 1

Each octet has 8 bits, with 1 signifying that bit in use, 0 signifying it not in use. Any value 00000000 - 11111111 inclusive is valid with 00000000 representing 0 and 11111111 representing 255.

00010111.01100000.00000000.00000000 (23.96.0.0 in DDN) 00000000.00000111.11111111.11111111 + (19 least significant or host bits) 00010111.01100111.11111111.11111111 = (23.103.255.255 in DDN)

---
Tags: network-topology, tcp
---


title: Big-Oh and Growth Rate

text:
# Question
Title: Big-Oh and Growth Rate
So, in the book I'm studying from it says :

> The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n).

What I understood from this statement is that since 9n is O(n), the growth rate of the functions 9n and n have the same growth rate, which does not make sense. I know that growth rate is the increase of a certain quantity over time. So, obviously the function 9n will grow way faster towards infinity, than the function n.

Did I understand the sentence given in the book incorrectly or is the statement incorrect?

# Answer
You understood it correctly, but have interpreted it differently than the book wanted it to be interpreted. You are right that $9n$ grows faster than $n$ so the main problem in your book may be trying to express a mathematical definition of $O$ with too few words.

**The definition**
The function $f(n)$ is in $O(g(n))$ if there exist $n\_0 \in \mathbb{N}$ and a positive real number $c$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n\_0$.

Now it is clearer how $9n$ is in $O(n)$. Because there exist, say $c=10$ and $n\_0=0$ such that $9n \leq c \cdot n$ for all $n \geq n\_0$.

**Why compare so loosely?**
The problem is, if we would compare growth rates by exact function values, then two very similar functions may not end up in the same class. For example, with your "strict-O notation"; for any function $d \> 0$, $f+d$ would not be in the same class as $f$, and that is not very useful. So, we have to draw the line somewhere (pun intended). Also, we use asymptotic analysis for describing algorithm complexity dependant on the input size $n$, and it is often not possible to calculate computation steps that precise.

**Other notations**
But, there are other asymptotic notations except big-O so you might want to look at those. You will find that $\Theta$ is, for example, more restrictive than $O$.
> 1 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?
The problem of determining, given a string $x$ and a context-free grammar $G$, whether $x \in L(G)$ is conjectured to take more than linear time in the length of $x$. Currently the best known algorithm is Valiant's which takes $\Theta(|G||x|^\omega)$.

On the other hand, for a fixed $G$ there may be a specialized recognition algorithm which is faster, and indeed linear-time algorithms have been developed for many grammars and classes of grammars of interest. In fact, I can't think of any example of a language which doesn't have a linear-time recognition algorithm.

Is there any example of a context-free language that is not known to be recognizable in linear time?

# Answer
Theorem 1 in "If the Current Clique Algorithms are Optimal, so is Valiant’s Parser" shows an explicit context-free grammar $G$ such that if $G$ can be parsed in linear time (or even a bit slower), then there's a surprisingly fast algorithm for the $k$-clique problem. As the paper says, no such algorithm for $k$-clique is known to exist and it would be a breakthrough if it was discovered; therefore, there's no known linear-time algorithm for this grammar $G$.
> 4 votes

---
Tags: context-free, parsers
---


# Question
Title: Proving irregularity of $\{a^nb^k \mid n > k \text{ or } n \neq k-1\}$
I need help with proving the following language is not regular: $$ L = \\{ a^n b^k \mid n \> k \\} \cup \\{ a^n b^k \mid n \neq k-1 \\} $$ My usual methods using pumping lemma are not getting me anywhere.

# Answer
> 1 votes
If $n \> k$ then $n \neq k-1$ (since $k-1 \not\> k$), so your language is really $L = \\{ a^n b^k \mid n \neq k-1 \\}$. If $L$ were regular then so would be the following language $a(a^\*b^\* \setminus L) \cup \\{\epsilon\\} = \\{ a^n b^n \mid n \geq 0 \\}$, which is known not to be regular.

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


# Question
Title: Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$?
Suppose we have a CNF formula $F$ and a permutation $\sigma$ of its literals such that for any literal $x, \sigma(\neg x)=\neg \sigma(x)$ and $F \vDash \sigma(F)$.

Does it hold that $F \equiv \sigma(F)$?

It is the case when $\sigma$ is a syntactic or even a semantic symmetry of $F$ but I don't know if it hold for any permutation that respects the hypothesis above.

# Answer
> 4 votes
The crucial observation is that if $A \vDash B$ then also $\sigma(A) \vDash \sigma(B)$. This follows since all $\sigma$ does is rename variables and flip some variables. For example, if $\sigma(x) = \lnot y$, $\sigma(y) = z$, and $\sigma(z) = x$, then $A(x,y,z) \vDash B(x,y,z)$ implies also $A(\lnot y, z, x) \vDash B(\lnot y, z, x)$.

Let $G$ be the set of all permutations of literals satisfying your condition. I claim that $G$ forms a group with respect to composition. Since $G$ is finite and composition is associative, it suffices to check that it is closed under composition. Indeed, if $\sigma(\lnot x) = \lnot \sigma(x)$ and $\tau(\lnot x) = \lnot \tau(x)$ then $\sigma(\tau(\lnot x)) = \sigma(\lnot\tau(x)) = \lnot\sigma(\tau(x))$.

Since $G$ is a group, $\sigma^{|G|}$ is the identity. If $F \vDash \sigma(F)$ then, applying $\sigma$ on both sides, we get $\sigma(F) \vDash \sigma^2(F)$. More generally, we get $\sigma^n(F) \vDash \sigma^{n+1}(F)$, and so $\sigma^n(F) \vDash \sigma^m(F)$ whenever $m \geq n$. In particular, choosing $n = 1$ and $m = |G|$, we obtain $\sigma(F) \vDash F$.

The group $G$ is known as the signed symmetric group, denoted $B\_n$, where $n$ is the number of variables.

---
Tags: permutations, propositional-logic
---


title: Selection Sort Analysis

text:
# Question
Title: Selection Sort Analysis
I'm having difficulty understanding the big-O analysis of the selection sort algorithm. Here is my pseudocode (with line numbers):

```
    procedure SELECTION (A(n), limit)
1.  for j <- 0 to limit - 1 do
2.      min_index <- j
3.      for k <- j + 1 to limit do
4.          if A(k) < A(min_index)
5.              min_index <- k
6.          end-if
7.      end-for
8.      temp <- A(min_index)
9.      A(min_index) <- A(j)
10.     A(j) <- temp
    end-for
end-SELECTION

```

Our professor wants us to work from the inside out; in other words, analyze the statements the furthest away from the conceptual vertical line that denotes hierarchies. Therefore, I start at line 5, and work out from there. Here's what I've understood so far:

* The time complexity of lines 4-6 is O(1) (constant).
* Because lines 4-6 are "contained" in the for loop on line 3, you must use the rule of sums to multiply line 3 and lines 4-6. In other words, if line 3 is a program fragment f(x) and lines 4-6 are a program fragment g(x), then the time complexity of lines 3 - 6 is f(x) * g(x).

This is where I get confused. Because `var limit` is referencing the size of the array, wouldn't the for loop on line 3 run `limit-1` times, because `k` is equal to 1 and is running to `limit`? To put it another way, if `k` were equal to zero, wouldn't the loop run `limit` times? Every video and website I've looked at has not given me a clear representation of that expression, because they've analyzed it differently.

On top of this question, how do I determine which asymptotic notation to use to describe this problem? Is it Big-Oh, Big-Omega or Big-Theta?

Thank you.

# Answer
> 1 votes
The number of iterations of the loop 3–7 depends on the value of $j$: it is $\mathit{limit} - j$. Therefore the running time of lines 3–7 is $O(\mathit{limit} - j)$. Lines 8–10 run in $O(1)$ time, so the body of the loop 1–11 runs in time $O(\mathit{limit}-j) + O(1) = O(\mathit{limit}-j)$ (using $j \< \mathit{limit}$). Finally, the total running time is $$ O\left(\sum\_{j=0}^{\mathit{limit}-1} \mathit{limit}-j\right) = O\left(\sum\_{j=1}^{\mathit{limit}} j\right) = O(\mathit{limit}^2), $$ using the formula $\sum\_{j=1}^n j = \frac{n(n+1)}{2}$.

---
Tags: algorithms, algorithm-analysis, time-complexity, runtime-analysis, sorting
---


# Question
Title: Closure of regular languages under deleting a 1 from each even run of 1s
> Let $R$ be a regular set over the alphabet $\\{0, 1\\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using closure properties for the class of regular sets.

Current Approach:

For the first part, using a machine construction, I was thinking that you take a simple FA that accepts only strings with an odd number of 1's (let's call this language $S$). This would be the simplest way of forcing strings in $R$ to have blocks of 1 of odd length. Then I would have some sort of $\epsilon/1$ transition to the original machines states where I would see if a string $x$ that is in the language $S$ would also be in $R$ if I were to add a 1 to any odd block of 1s.

I am unsure of how to describe that using the 5-tuple, $M = (Q, \\{0,1\\}, \delta, q\_0, F)$, or if my methodology is correct. Any advice on where I should go and how I might prove closure in the two different ways is welcome.

# Answer
> 4 votes
Below you can find solutions for the similar problem in which we want to delete a single 1 from each *odd* length run of 1s. I'll let you adapt them to your question.

First, let me explain how to solve it using closure properties. We start with your language $R$. We then apply a regular substitution that optionally "marks" every 1, i.e. changes it into $\mathbf 1$. We intersect the resulting language with $0^\*((11)^\*(\mathbf{1}+\epsilon)0^+)^\*((11)^\*(\mathbf1+\epsilon)+\epsilon)$ – this has the effect of marking the final 1 out of each odd run. Finally, we apply a homomorphism that deletes all marked 1s.

Second, let me explain how to explicitly construct an NFA for the new language given an NFA for $R$. Let the NFA for $R$ be $\langle Q, \\{0,1\\}, \delta, q\_0, F \rangle$. The new states will be $(Q \times \\{0,1\\}) \cup \\{q\_f\\}$, and the new initial state will be $\langle q\_0, 0 \rangle$; the second entry is the parity of the current run of 1s. The new accepting states are $(F \times \\{0\\}) \cup \\{q\_f\\}$ (note that in the new language, all runs of 1s must have even length). It remains to define the new transition function:

* If there is a transition $q\_1 \stackrel 0 \to q\_2$, then we add a transition $\langle q\_1, 0 \rangle \stackrel 0 \to \langle q\_2, 0 \rangle$; that is, we allow the transition only if the parity of the current run of 1s is even.
* If there is a transition $q\_1 \stackrel 1 \to q\_2$, then we add the following transitions:
    1. $\langle q\_1, 0 \rangle \stackrel 1 \to \langle q\_2, 1 \rangle$ and $\langle q\_1, 1 \rangle \stackrel 1 \to \langle q\_2, 0 \rangle$; these just maintain the parity of the length of the run.
    2. If $q\_2 \in F$: $\langle q\_1, 0 \rangle \stackrel \epsilon \to q\_f$. This handles odd runs of 1s at the very end of input.
* If there are transitions $q\_1 \stackrel 1 \to q\_2 \stackrel 0 \to q\_3$, then we add the transition $\langle q\_1, 0 \rangle \stackrel 0 \to \langle q\_3, 0 \rangle$. This corresponds to deleting a 1 from the end of an odd run.

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


# Question
Title: Proving formula for derivative of Kleene star
> Prove that for any symbol $a$ and regular expression $r$ it is true that:
>
> $$\partial a(r^\* ) = \partial .a(r)(r^\* )$$

My attempt:

Induction on regular expression $r$

Base cases:

1) $\emptyset $

$\partial a(\emptyset^\* ) = \partial a(\varepsilon) = \emptyset$

$\partial a(\emptyset) (\emptyset^\* ) = \emptyset \emptyset^\* = \emptyset \varepsilon = \emptyset$

2) $\varepsilon $

$\partial a(\varepsilon^\* ) = \partial a(\varepsilon)$ = $\emptyset$

$\partial a(\varepsilon) (\varepsilon^\* ) = \emptyset \varepsilon^\* = \emptyset \varepsilon = \emptyset$

3) $a\in\Sigma$

Case $a=b$:

$\partial a(a^\* ) = $

$\partial a(a) (a^\* ) = \varepsilon (a^\*) = a^\*$

Case $a \neq b$:

$\partial a(b^\* ) = $

$\partial a(b) (b^\* ) = \emptyset (b^\*) = \emptyset$

But how to prove for Inductive Step when regular expression $r$ is:

1) Concatenation: $r=\alpha\beta$

2) Union: $r=\alpha + \beta$

3) Kleene Star: $r=\alpha^\*$

# Answer
> 1 votes
Using structural induction seems like overkill, or, which is more likely in your case, overly formal in a way which complete obstructs what is going on.

Here is a simple proof that explains why $\partial\_a(r^\*) = \partial\_a(r)r^\*$. We consider two cases:

1. $\epsilon \notin L\[r\]$. This implies that $\partial\_a(r^{n+1}) = \partial\_a(r)r^n$. Since $\partial\_a(\epsilon) = \emptyset$, we get $$ \partial\_a(r^\*) = \bigcup\_{n \geq 0} \partial\_a(r^n) = \bigcup\_{n \geq 1} \partial\_a(r)r^{n-1} = \partial\_a(r) \bigcup\_{n \geq 1} r^{n-1} = \partial\_a(r) r^\*. $$
2. $\epsilon \in L\[r\]$. Write $r = \epsilon + s$, where $\epsilon \notin L\[s\]$. Then $r^\* = s^\*$, and so using the preceding case applied to $s$, we get $$ \partial\_a(r^\*) = \partial\_a(s^\*) = \partial\_a(s)s^\* = \partial\_a(r)r^\*, $$ since $\partial\_a(r) = \partial\_a(\epsilon) \cup \partial\_a(s) = \partial\_a(s)$.

---

If you did want to use a proof by structural induction, then you would need to let us know what identities of the Brzozowski derivative and of regular expressions you are allowed to use.

For example, if you are allowed to use $\partial\_a(L\_1 \cup L\_2) = \partial\_a(L\_1) \cup \partial\_a(L\_2)$, then you immediately get the inductive step for union.

As another example, for the base case $r = b$, you can use the fact that every word in $b^\*$ is either empty or starts with a $b$, and consequently $\partial\_a(b^\*) = \emptyset$. Since also $\partial\_a(b) = \emptyset$, you would deduce this base case. Perhaps the identities you are allowed to use can implement this argument.

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


title: DFA that accepts a*b*c*

text:
# Question
Title: DFA that accepts a*b*c*
Beginner in DFA related studies, was trying to figure out how to create a DFA with {a,b,c}, that can recognize a * b * c \*.

Appreciate the help.

# Answer
> 2 votes
Here is a possible DFA:

Basically, just send any invalid string like baa*c*, caa\*, etc. to a junk state.

As suggested by Yuval Filmus, you can minimize the number of states further by merging $s$ and $a$ :

# Answer
> 0 votes
This seemed to have done the job

---
Tags: finite-automata
---


# Question
Title: How many bits representation of data on tape of Turing machine consumes
I am wondering how to represent *signed number*, *vector*, *matrix* on binary tape of Turing machine to consume the smallest possible amount of memory.

For signed number it is obvious: encode sign as a single bit and sum it with the length of number representation $\lceil\log\_2(\mathrm{abs}\\,(n)+1))\rceil$.

But how is it possible to represent a vector of numbers with different size. How to consume minimal amount of memory?

# Answer
Note that the usual representation of signed integers in binary is not the one you propose.

In general, though, being super-efficient about coding in Turing machines isn't really important. We mainly use Turing machines for:

* computability, where we don't care about efficiency *at all*;
* complexity, where we only care about efficiency up to constant or even polynomial factors.

We don't use Turing machines for real computation where we care about the "real" efficiency, where making your program twice as fast makes it twice as good.

So, from the point of view of Turing machines, it's completely adequate to code vectors and so on by something like the following. Pick any sensible format for the individual data items and write those out with each bit doubled (i.e., $1011$ becomes $11001111$). Then separate each item with $01$. This means that storing the vector/matrix/whatever takes "twice as many bits as it should" but that constant factor just isn't important for the things we use Turing machines for.
> 1 votes

# Answer
I see 3 ways of doing it:

1. Storing the length and the items
2. Storing a bit after each item indicating whether it's the last item (can't store the empty list)
3. Storing a bit before each potential item indicating whether there are any more items

BTW, I think your number representation has no way to figure out where it ends.
> -1 votes

---
Tags: turing-machines, encoding-scheme
---


# Question
Title: "Famous logicians have made embarrassing errors here," a line from SICP. What is this referring to?
Here is the context (*Structure and Interpretation of Computer Programs*, section 1.1.8, under heading "Local names"):

> A formal parameter of a procedure has a very special role in the procedure definition, in that it doesn't matter what name the formal parameter has. Such a name is called a *bound variable*, and we say that the procedure definition *binds* its formal parameters. The meaning of a procedure definition is unchanged if a bound variable is consistently renamed throughout the definition.

At the end of that last line, there is a footnote (26), which says:

> The concept of consistent renaming is actually subtle and difficult to define formally. Famous logicians have made embarrassing errors here.

What or who is the text referring to? Why would defining "consistent renaming" be hard, which logicians have made errors trying to define this, and what were those errors?

# Answer
> 11 votes
This is a partial answer: I have no idea about which errors or people SICP is referring to. I can only provide some hints about "why" variable renaming can be painful to handle precisely.

First of all, it does seem trivial to define. For instance, we can rename bound variables in indexed sums

$$ \sum\_x e = \sum\_y (e\\{y/x\\}) $$

where $e$ is any expression, and $e\\{y/x\\}$ denotes the syntactic replacement of each $x$ with $y$. Trivial, right?

Well, if we blindly apply the rule above, we get

$$ \sum\_x (x+y) = \sum\_y (y+y) $$

That's not good. We need to add the requirement "$y$ does not occur in $e$", or we get a name clash.

Now, consider this correct renaming

$$ \sum\_x \sum\_y (x+y) = \sum\_x \sum\_z (x+z) $$

if we want to rename $x$ into $y$, by the rule above we can do it on the right hand side, but not on the left hand side. That's inconvenient, since the two differ only by a renaming, so they should be handled in the same way.

A typical approach here is to resort to redefining $e\\{y/x\\}$ as "capture-avoiding substitution", and relax the requirement "$y$ does not occur in $e$" and use instead "$y$ does not occur *free* in $e$".

We then define free occurrences:

$$ free(x)=\\{x\\} \qquad free(e+t) = free(e)\cup free(t) \qquad free(\sum\_x e) = free(e)\setminus\\{x\\} $$

Finally, capture avoiding substitution:

* $x\\{t/y\\}$ is $t$ if $x=y$, and $x$ otherwise.
* $(e+e')\\{t/y\\} = e\\{t/y\\} + e'\\{t/y\\}$ (easy case)
* $(\sum\_x e)\\{t/y\\} = ??$

The last case is painful. If $x=y$, the substitution is no-op, since we want it to affect free variables only, and $x$ is bound. So the result is just $\sum\_x e$.

If $y\neq x$, we would like to say that $(\sum\_x e)\\{t/y\\} = \sum\_x (e\\{t/y\\})$. This however is wrong, in general, since if $x$ occurs free in $t$ we get a capture.

Sigh. So, we let $z$ to be the "first" variable which is 1) not $y$, 2) not free in $t$, and 3) not free in $\sum\_x e$. Here, "first" means that we need to well-order the set of variable names (e.g. by picking a bijection between names and naturals). Then, we finally let $(\sum\_x e)\\{t/y\\} = \sum\_z (e\\{z/x\\}\\{t/y\\})$.

I hope I got it right. (My first attempt was wrong, by the way)

Some authors consider more cases, but the result is the same "up to renaming". The choice of the "first" $z$ does not really matter above: any such $z$ would work fine, and lead to the same result (again, up to renaming).

Now, finally, we have a sound definition of renaming ($\alpha$-conversion) and capture-avoiding substitution of a free variable. Above, I considered sums, but they apply to all binders (e.g. $\lambda x$ in the lambda calculus, function definitions in many PLs, etc.).

Now, imagine having to deal with this intricate definition every time we want to *prove* something in PL theory. We could, but we do not want to. It's boring, tedious, error-prone, clutters the proof and provides no insight to the reader. For this reason, many PL authors simply skip the details by saying (or even taking as granted!) that terms are to be taken "up to variable renaming", that all bound variables are assumed distinct from whatever they need to be distinct from, that we assume the "Barendregt convention", or something to the same effect.

To be brutally honest, this is cheating in proofs. We could also add "wink wink, nudge nudge, say no more!" in the same spirit. We essentially ask for mercy and tell the reader: "look, this is boring, I do not want to do it, you do not want to read it -- we both know that, with a huge effort, we could rewrite this proof to include all the details".

Technically, it *is* possible to exploit this shortcut to prove a false statement. The experienced proof reviewer, however, knows what is "morally fine" and could made perfect (with great effort), and what is suspicious. The latter could include something which depends on the actual choice of *bound* names (so we are *not* really working "up to" as promised!). In those cases, the review will ask for more details, so that (s)he can be convinced.

---
Tags: logic
---


# Question
Title: Why is an accurate time so important for servers and computers?
I just saw this short documentary about atomic clocks. The person working for the Atom clock company gets asked what would happen is all the atom clocks would be turned off and he replayed that cell phone services and the internet would stop working. I have read that an accurate time is important but do not now why.

Why is an accurate time so important for servers and computers and why would these services stop working?

# Answer
> 2 votes
It depends. If all atomic clocks would be turned off simultaneously, right now, that would be trouble. Because everyone *relies* on atomic clocks. And everything is organized in such a way that it doesn't matter much if a handful or two dozen stop working, but if they all stop working, then all the time servers in the world have no source for their time anymore.

If you announced that exactly three months from now all atomic clocks will be turned off, that would be a lot of work setting up some slightly less precise clocks, and to switch over to those less precise clocks, but cell phone service and internet would happily continue working. Even a quartz wall clock (like the one in your office) can be precise within 0.2 parts per billion. Taking 1,000 such wall clocks and carefully averaging their time would be quite accurate, and surely we can build a quartz clock for 100,000 that is a lot more precise than one that costs 100.

The problem is not the precision. The problem is that if you turn off all atomic clocks *right now* then we don't have anything to replace them *right now*. There are about 400 atomic clocks in the world. If we had 400 state of the art quartz clocks ready to be used as replacement automatically if the atomic clocks are stopped, then there would be no problem except for very few very special use cases.

---
Tags: clocks
---


# Question
Title: Mathematically calculating time complexity
This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked **a lot**, but it didn't make me understand fully the subject.

Also I understand that it's impossible to calculate every function, but usually we can (otherwise we have not been asked to do so on the exam).

I know how to mathematically calculate the time complexity of the following function:

```
for(i = 0; i <= n-1; i++) {
    for(j = i + 1; j <= n - 1; j++) {
        // loop body - const O(1)
    }
}

```

I would calculate it as following: (hope without mistakes)

$$\begin{align\*} \sum\_{i=0}^{n-1}\sum\_{j=i+1}^{n-1}1 & \overset{(1)}{=}\sum\_{i=0}^{n-1}((n-1)-(i+1)+1)\\ &=\sum\_{i=0}^{n-1}(n-i-1)\\ &=n\cdot\sum\_{i=0}^{n-1}1-\sum\_{i=0}^{n-1}i-\sum\_{i=0}^{n-1}1\\ &\overset{(2)}{=}n\cdot\sum\_{i=0}^{n-1}1-\sum\_{i=1}^{n-1}i-\sum\_{i=0}^{n-1}1\\ &\overset{(1)}{=}n\cdot((n-1)-0+1))-\sum\_{i=1}^{n-1}i-((n-1)-0+1)\\ &=n^{2}-n-\sum\_{i=1}^{n-1}i\\ &\overset{(2)}{=}n^{2}-n-\frac{(n-1)\cdot n}{2}\\ &=\frac{2n^{2}-2n-n^{2}+n}{2}\\ &=\frac{n^{2}-n}{2}\\ &=O(n^{2}) \end{align\*}$$

when I use the following equations:

$$\sum\_{i=m}^{n}1=n-m+1 \\,\\,\\,(1)$$ $$\sum\_{i=0}^{n}i=\sum\_{i=1}^{n}i=\frac{n(n+1)}{2} \\,\\,\\,(2)$$

But when I get across with much harder function, as following:

example 1:

```
int x = 2;
while (n < x) {
    x *= x;
}

```

example 2;

```
int i = 1;
while(i < n) {
    if((n – i) % 2)
        i *= 3;
    else
        i *= 2;
 }

```

I get lost. I really don't know where to start calculating. I always can start inserting different values for `n`, and guessing the time complexity, but it does not feels right (and also it can be misleading).

Is it even possible to mathematically calculate the time complexity of those examples? how should I approached those questions? Maybe is there somewhere a list of possible tricks?

# Answer
> 1 votes
If we ignore effects of overflow and assume we can square x as often as we like in constant time, then the first example clearly either stops immediately if n ≥ 2, or runs forever if n \< 2.

In the second example, at each iteration i is multiplied either by 2 or by 3. Therefore after k iterations, $2^k ≤ i ≤ 3^k$. The number of iterations until i ≥ n is between $log\_2 (n)$ and $log\_3(n)$ which is in each case $O (log(n))$.

On the other hand, I'm currently working on an algorithm where I don't have the slightest idea how to calculate the runtime, although measurements show that it takes experimentally about $600 n^{1/2}$ nanoseconds for values from $10^{12}$ to $10^{19}$ \- with huge variations. A proof for $O(n^{1/2})$ is mathematically beyond me.

In the end, this question is like asking "how can I prove mathematical theorems". Some are easy, some are hard, most get easier with practice. There is no "list of possible tricks". The most helpful thing is that when you are concerned with big-O notation you don't need *precise* results. A constant factor makes no difference.

---
Tags: time-complexity, asymptotics, mathematical-programming
---


# Question
Title: what is the time complexity for binary division by repeated subtraction?
The divisor and dividend are of length n and m bits respectively.

According to Wikipedia article, https://en.wikipedia.org/wiki/Output-sensitive\_algorithm division by substraction is an output sensitive algorithm and has the time complexity of Θ(Q). Can the time complexity be calculated in terms of length of input bits?

# Answer
> 0 votes
If you calculate Z = floor (X / Y) by repeated subtraction, then you will perform Z subtractions. If you divide exactly n bits by exactly m bits, then there are at least $1/2 \cdot 2^{n-m}$ and at most $2 \cdot 2^{n-m}$ subtractions, so it's $\theta (2^{n-m})$ subtractions.

If you divide at most 2 bits by at most m bits, then Y might be 1 and in the worst case there are almost $2^n$ subtractions, so $O(2^n)$ subtractions.

---
Tags: asymptotics, runtime-analysis
---


# Question
Title: Is there a measure of space usage over time?
We typically measure algorithm efficiency by space efficiency and then time efficiency e.g. this algorithm takes O(n) time and O(n) space. However, I feel this does not capture the full story.

Say we have a process that looks like this. Assume memory allocation is O(1) time complexity for simplicity.

```
process(n):
  mem = allocate(n)
  for 0 to n:
    ... do O(1) stuff
  end
  free(mem)
  end

```

The above process takes O(n) time and O(n) space.

Here's another process that takes O(n) time and O(n) space.

```
process(n):
  for 0 to n:
    ... do O(1) stuff
  end
  mem = allocate(n)
  ... do O(1) stuff
  free(mem)

```

In the both processes you're using O(n) space. In the first one you're using the space over the course of the entire process. In the second, you're using it only at the very end. Is there a way to formalize the difference?

# Answer
Sure. Of course, you are absolutely right, that time complexity and space complexity don't capture the whole story. No one metric is likely to.

There are many ways one could plausibly distinguish between those two programs. For instance, one could ask about average space usage (averaged over the lifetime of the program). These metrics might be harder to use, but might be more relevant in some situations. Only you can know what you want to optimize, so you only you can determine which metric is most suitable for your particular situation. You might find that asymptotic analysis is not the best tool for the job and instead you want to measure space usage on a real-world benchmark/workload. That is also reasonable.
> 4 votes

---
Tags: algorithm-analysis, space-analysis
---


# Question
Title: Problems with decidability open (for a long time) proven decidable
It seems to me that problems whose dedicability remains open for a long time, if resolved, tend to end up being undecidable. A prominent example would be (e.g.) Hilbert's tenth problem, whose decidability was open 21+ years (†) until proven decidable. Is there a similiar example of a problem whose decidability was open for a long time (receiving considerable attention) but was proven, in the end, to be decidable?

---

(†) Hard to put an exact figure on how long it was open. Originally stated in 1900 and proven in 1970, but the original statement was before the modern notion of undecidability.

# Answer
I suspect there are many of them. Pick almost any recent paper that shows decidability of some problem, and I suspect chances are good you'll have an example. So, I doubt your heuristic that if decidability remains open for a long time, chances are that the problem is undecidable.

For example: The matrix mortality problem for non-singular 2x2 matrices was recently shown to be decidable (Decidability of the Membership Problem for 2 × 2 integer matrices, Potapov, Semukhin).
> 2 votes

---
Tags: undecidability, history
---


# Question
Title: Graph Traversal Solutions for "Find all unique paths" Problem
I was studying the grid problem where a robot is at the top left position and wants to go to the bottom right position and you need to return the number of unique paths it can take to get there with the constraint that it can only move down or to the right.

It looks like the standard way to solve this is with the top-down dynamic programming approach but I was wondering if a graph traversal algorithm could also work.

The problem with graph traversal algorithms is that you do not revisit nodes that you have already seen but many unique paths can visit the same node. So if you got rid of the constraint that you cannot revisit a node, would a graph traversal method work here? This is also a special case where you cannot get stuck in an infinite loop because the robot can only go down or right so it can never go back to a node it has already been to.

# Answer
> 1 votes
There could be many paths. For example, if the grid is $n \times n$ and all edges are present, then there are $\binom{2n}{n} = \Theta\left(\frac{2^n}{\sqrt{n}}\right)$ paths. You don't want to be going through all of them. Using dynamic programming, you can come up with the answer without going over all paths individually. In other words, dynamic programming is much more efficient than your suggested algorithm.

---
Tags: dynamic-programming, graph-traversal
---


# Question
Title: difference between minus and subtract microoperation
While reading Computer Architechture book by M.Mano. I came across Arithmetics Microoperations sections which has two microoperations which confuses me a lot,

R3 \<- R1 - R2 ( Minus Microoperation )

R3 \<- R1 + complemented(R2) + 1 ( Subtract Microoperation ).

Can someone tell me the difference?

# Answer
Suppose we're working with unsigned bytes, e.g. modulo 256.

Let's say R1 = 100 and R2 = 70. Direct subtraction should give us 100 - 70 = 30:

```
01100100
01000110 -
========
00011110

```

Modulo 256, subtracting 70 is the same as adding 256 - 70 = 186, because -70 *is* +186. The complement of 70 is 255 - 70 = 185, which is just one less. Therefore, the following sum produces 100 + 185 + 1 = 286 which is the same as 30 (modulo 256). Of course, the ninth bit 'falls off' when doing 8-bit arithmetic, so we get 30 as a result.

```
 01100100
 10111001
 00000001 +
 ========
100011110

```

So both methods give the same result, just in a different way.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: What is the difference between the study of Evolutionary algorithm vs. Optimization?
I have a course named "Evolutionary Algorithm". But, our teacher is always mentioning the word "Optimization" in his lectures.

I am confused. Is he actually teaching Optimization? If yes, why is the name of the course not "Optimization"?

What is the difference between the study of Evolutionary algorithm and Optimization?

# Answer
Indeed, in evolutionary algorithms, you are optimizing an objective function. Hence, evolutionary algorithms are algorithms for optimization. Hence, they are the specific case of optimization methods. However, there are a vast variety of optimization methods that are not an evolutionary algorithm (such as simplex methods in OR, Lagrange methods and so on). See more about the evolutionary algorithms here:

> In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based **metaheuristic optimization algorithm**.
> 2 votes

---
Tags: algorithms, optimization
---


title: Reducing INDSET and MAXCUT to 3SAT

text:
# Question
Title: Reducing INDSET and MAXCUT to 3SAT
Given a graph and an integer $k$ is there an independent set larger than $k$ is INDSET problem and is there a cut larger that $k$ is the MAXCUT problem. Is there standard way to convert to 3SAT from these problems that preserves number of solutions? I have only seen reductions other way in standard texts. Since all these are NPC there should be a way to convert back.

# Answer
$\mathcal{INDSET}$ $\leq\_p$ $\mathcal{3SAT}$:

For each vertex $v\in V$, create a Boolean variable $x\_v$.

For each edge $uv\in E$, create a clause $\lnot x\_u \lor \lnot x\_v$

Now, to assure that there exist exactly (or more than) $k$ variables assigned to $\mathrm{TRUE}$, we need to sum over all the assigned value ($\mathrm{FALSE}$ as $0$, $\mathrm{TRUE}$ as $1$):

We use half-adder and full-adder. Note that each circuit gate using some Boolean operation like $C = A \oplus B$ can be transformed into $\mathcal{3SAT}$ clauses easily.

To compare the obtained sum and $k$, it is straightforward from their binary representations (as two arrays of Boolean variables), just scan from left to right (in big-endianness fashion).

$\mathcal{MAX-CUT}$ $\leq\_p$ $\mathcal{3SAT}$:

For each vertex $v\in V$, create a Boolean variable $s\_v$. A cut is then described by a partition of the vertex set $V=S\cup (V\setminus S)$, where $v\in S$ iff. $s\_v=\mathrm{TRUE}$.

For each edge $e=uv\in E$, create a Boolean variable $c\_e$ and some clauses to force that $c\_e=(s\_u\neq s\_v)$. So, $c\_e=\mathrm{TRUE}$ iff. $e$ is crossing $(S, V\setminus S)$.

Then, we use half-adder and full-adder as before to count the number of crossing edges. Lastly, compare as before.
> 1 votes

---
Tags: np-complete, reductions, satisfiability, np, max-cut
---