# Question
Title: What is the formal, rigorous definition of a programming language?
In programming language theory, people study the theory behind programming languages. But I have never heard any formal definition of programming languages themselves. What is the formal definition, not of a particular programming language like Python or C++, but of programming languages themselves?

# Answer
> 40 votes
To taper expectations a little bit, I will first note that the term "programming language" is deliberately broad: it is intended to be open to some interpretation. It means, no more and no less, any convention that is used for describing instructions for computers to execute. This includes, for example, not just C++ and Python, but also things like Nondeterministic programming, where we actually don't tell the computer exactly what to do, but give it several alternatives and allow it to choose any one of them; declarative logic languages like Datalog where we give the computer a set of logical axioms and ask it to deduce all the true statements from those axioms; and even very low-level descriptions like Turing machines and electrical circuits, where we give the program explicitly as electrical or mechanical components. All of these are ways of describing instructions to computers, so all are valid programming langauges at very different levels of abstraction.

However, programming languages researchers do generally agree on some common formal components of programming languages that should always be present, and these serve as a general definition. Namely: every programming language is defined by a **syntax** and a **semantics.**

* **Syntax.** This is a formal grammar which gives the set of programs that can be written. Importantly, the formal grammar consists of finitely many syntax elements, which are described in terms of other syntax elements. For example a simple grammar is:

```
Variable := x | y | z
Term := 0 | 1 | Term + Term | Variable
Program := set Variable = Term | return Term | Program; Program

```

In this simple language, we have three syntax elements: Variables, Terms, and Programs. In a formal grammar, each syntax element has finitely many cases for how it can be constructed via other syntax elements. For example, a program is either an assignment (setting a variable to equal a term, e.g. `set x = x + 1`), a return statement, or a sequence of two programs which should be executed one after the other.
* **Semantics.** Syntax is just describing the set of valid programs; but it doesn't say anything about what those programs *mean*. Semantics is a way of assigning meaning to programs. Unlike syntax, which is almost always given as a formal grammar as above, semantics can be given in at least two different ways: these include "denotational semantics", where we assign a mathematical object such as a function to each program, or "operational semantics", where we describe the execution of a program in a more true-to-life way as a sequence of steps.

To illustrate this, starting with denotational semantics: we would say that the term `3 + 5 + 8` is assigned the meaning of `16`. More interestingly, the program `set x = x + 3 + 5` is assigned the meaning of the mathematical function mapping every integer to that integer plus 8.

Operational semantics, on the other hand, is very different. We would say that the term `3 + 5 + 8` evaluates to `8 + 8` which in turn evaluates to `16`. We would also say that the program `set x = x + 3 + 5` in a context where x = 5 evaluates to a context where x = 13. So, instead of giving a meaning to each term or program itself, we give a meaning between terms called "evaluates to": we give a formal definition of what it means for `A` to evaluate to `B` in the context `C`.

In any case, the *semantics* of a language, whether denotational or operational (or something else) *gives meaning* to the symbols and allows us to make sense of what programs compute, not just what they look like.

Putting these together, we get the following definition.

**Definition:** A *programming language* consists of (1) a syntax, given as a formal grammar; and (2) a semantics, given either as denotational semantics which gives a meaning to each syntax element, or an operational semantics which says when two programs or program contexts relate.

# Answer
> 3 votes
I think it is very hard to give a definition that is both general, formal, and not too general. And I don't think I've seen any attempts. Nevertheless, here is an attempt at a mathematical definition.

> A *programming language* consists of a set of programs $P$ such that each element of $P$ is finite and for each element $p$ of $P$ there is triple $m(p) = (I,O,f)$ such that $I$ and $O$ are sets and $f$ is a relation between $I$ and $O$ such that for each $I$ there is at least one related $O$.

The idea is that $m(p)$ is the meaning of program $p$, $I$ is its set of inputs, $O$ is its set of outcomes, $f$ gives, for each input, the set of possible outcomes that might result from that input.

Note that the elements of $I$ and $O$ need not be finite. The restriction that the elements of $P$ be finite is arbitrary and I only put it there, because I don't think that a programming language that has infinitely large programs would be very useful. The restriction that for each input there should be at least one outcome is the "no miracles" healthiness condition. That means that we need one or more outcomes to represent nontermination, at least, when the program might not (or must not) terminate for some inputs.

Here are three objections to this definition.

**It's too general:** One problem with this definition (and I suspect any improvement to it) is that many things we don't think of as programming languages can be made to fit it. Here are two examples

* HTML (without JavaScript) is a programming language by this definition. Some people would say that's not right because HTML is formatting language rather than a programming language.
* We can imagine a programming language that contains a program $h$ such that $m(h) = (T, \\{true, false\\}, f)$ where $T$ is the set of all Turing Machines, and $f$ maps $t \in T$ to $true$ if $t$ halts when started on an empty tape and maps $t$ to $false$ if $t$ doesn't halt when started on an empty tape; some people would say that's no programming language.

The response is that you can make further restrictions as needed. E.g., you can define the set of all Turing-complete programming languages by making suitable refinements.

**It's not general enough:** For some things that seem like programming languages it might take some creativity to fit them into this framework. For example for a probabilistic programming language the outcomes would need to be probability distributions. A better approach might be to abandon this definition and use suitable generalization of relations. Similar remarks apply to quantum computing.

The response is that the examples given show it might be awkward to fit some languages to the definition.

**It misses that programming languages have variants:** Real programming language definitions are often parameterized. For example in C `int i = 10 * 1000 * 1000 * 1000 ;` has undefined behaviour on some implementations and is well defined on others; it depends on choices that are up to the implementer. My definition doesn't capture that idea.

The response is that it's easy to generalize the definition by adding another input to the $m$ function representing the variant of the language or (by Currying) to think of a language like C as being a function from a set of choices to a language of the sort defined here.

Three books that explore ideas along these lines are

* Hoare and He, *Unifying Theories of Programming*
* Francez, *Program Verification*
* Hehner, *a Practical Theory of Programming*

# Answer
> 1 votes
Note that programs in a programming language don't need to be written down as text, there are programming languages that use graphs instead. So anything that restricts programming languages to text is not a formal, rigorous description of a programming language.

Note that for many text-based programming languages, the set of programs in the language cannot be described by a grammar alone. Many programming languages have additional rules that cannot or are not expressed by a grammar.

Note that for many text-based programming languages, programs are not described by *one* string, but by one or more strings, stored in files. For example, static items in C or C++, fileprivate items in Swift, are based on the concept of having multiple files that are combined.

Note that many programming languages include a "standard library", which is part of the language. And many programming languages assume that there is a "standard environment" in which they work.

Note that many programs do *not* process text based input and produce text based output. Instead the process inputs from a huge range of input mechanisms and produce an effect using a huge range of output mechanism.

So all in all, you will have a very hard time finding a rigorous and formal definition of programming languages, that works with actual programming languages that are in daily use.

# Answer
> 0 votes
Look what I found https://en.wikipedia.org/wiki/Programming\_language

> A programming language is a formal language comprising a set of instructions that produce various kinds of output. Programming languages are used in computer programming to implement algorithms.

# Answer
> 0 votes
A programming language is one which can be encoded by a formal system; for example, through a Backus-Naur form which is a common technique for describing context-free grammars.

However, I'd say, it is only a *potential* programming language until there is hardware that can interpret and run it. At bottom this is a Turing machine. Theoretically speaking, we can identify the two.

It's worth noting that a programming language by this definition may not be very practical and which is an important consideration for programming languages in practise. However, the point of describing programming languages theoretically is to theorise with them, so the simplest possible definition here is usually the most effective. After all, this is one reason why we use a Turing Machine to model computation and not some more complex machine.

---
Tags: programming-languages
---


# Question
Title: Is there any field that studies the equivalent of cellular automata, but for arbitrary graphs rather than 1D cells?
A cellular automaton consists of a sequence of cells, each with a state, and a globally symmetric transition rule based on the neighbors of a cell. They can be interpreted as graphs where each cell is a node, and each node has an edge to a neighbor.

Is there any field studying that system, but generalized to arbitrary graphs - i.e., allowing cells to have, for example, 3 or more neighbors?

# Answer
Graph dynamical systems is a general term for systems where each vertex of a graph carries a state, and the system evolves in time so that the next state of a vertex only depends on the states in its neighborhood (possibly in a nondeterministic way). Boolean networks are a special case where the graph is finite and each state is either $0$ or $1$. Boolean networks are used e.g. as models of gene expression in cells, and a lot of practical and theoretical research exists on them.
> 1 votes

---
Tags: graphs, cellular-automata
---


# Question
Title: Can a regular expression be any string from the language described by it?
Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?

# Answer
Your question is unclear. However "a language (that has strings of infinite length)" cannot exist. By definition a language only contains words of finite length.

Let $\Sigma$ be a (finite) alphabet and $\epsilon$ denote the empty word. A language is a subset of $\Sigma^\*$, where $\Sigma^\*$ is defined as $\Sigma^\* = \cup\_{i=1}^{\infty} \Sigma^i$, $\Sigma^0 = \\{ \epsilon \\}$, and $\Sigma^i = \\{xy : x \in \Sigma^{i-1}, y \in \Sigma\\}$ for $i\>0$.

As you can see, a string of infinite length does not belong to any $\Sigma^i$ and therefore it belongs to neither $\Sigma^\*$ nor to any of its subsets.
> 1 votes

# Answer
Don't know exactly what you mean, but a is an element of L(a). Actually the only element of L(a). (while a\* is not an element of L(a\*) because none of the elements contain the symbol \*).
> 0 votes

---
Tags: regular-languages, regular-expressions
---


title: Chebyshev inequality comparison

text:
# Question
Title: Chebyshev inequality comparison
Given $n$ distinct values $(x\_i)\_{i=1}^{n}$ with mean $\mu$ and standard deviation $s$, for all $i$, we have $|x\_i−\mu| ≤ s \sqrt{n − 1}$. How does this inequality compare with Chebyshev inequality as $n$ increases?

# Answer
> 1 votes
Chebyshev's inequality states that $$ \Pr\[|x\_i - \mu| \> c\sigma\] \< \frac{1}{c^2}. $$ Choosing $c = \sqrt{n}$, we deduce that with positive probability, $$ |x\_i - \mu| \leq \sqrt{n} \cdot \sigma \text{ for all } i. $$

---
Tags: statistics
---


title: object image segmentation

text:
# Question
Title: object image segmentation
I have 2 different datasets with similar objects, one where each object is 50 pixels wide and the other where they are 150 pixels. Each photo is 512x512 for both datasets. These two datasets have the same number of photos. Taken with the same camera, so same focal length, resolution etc...

So far, we agree that only the size of the objects differs.

---

I segment with U-net, for each dataset. It's all right, I have good predictions.

For fun, I train with 150 pixels dataset and test on 50 pixels dataset, and vice versa.

Again, everything is fine, the results are bad so we deduce that the results are better when the size of the objects is similar. Logical.

---

Now I train a model on a dataset composed of both the 50 and 150 pixels objects (half 50 and half 150), and in total the same number of images as before.

When I test my model on a set of the images composed exclusively of 50 pixels objects (respectively 150), I get better results than when I trained my network using only 50 pixels object to train (resp 150)

Is this due to scale-(in)variant features issues? Is there a similar case you dealt with ?

Thanks a lot

# Answer
> 2 votes
That's a tough one. I don't know what could cause that.

It can be hard to know why we see the results we do, when working with neural nets. Often the best we can do is form several hypotheses, and then devise experiments to try to test those hypotheses.

Some possible explanations that you could try to test:

* Perhaps it is noise / random chance
* Perhaps the 50-pixel images are fairly homogenous and the 150-pixel images are fairly homogenous, and taking a combination of these two yields more diversity, which helps the network learn (e.g., it doesn't overfit to either)
* Perhaps the 50-pixel objects don't come from the same distribution as the 150-pixel objects (e.g., the 50-pixel images are of children and the 150-pixel images are of adults; these differ in more ways than just size; or the background is correlated to the size of the object), and you get more regularization from exposing the network to both, or something (this is vague and might not be very different from the second explanation)

Maybe you can think of other possibilities.

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states
Let $L$ be a language, and consider the following relation $\equiv\_L$ on strings: $s\_1 \equiv\_L s\_2$ if and only if, for every string $w$, we have that $s\_1w \in L \Leftrightarrow s\_2w \in L$. This is an equivalence relation.

Let $I(L)$ be the number of equivalence classes of $\equiv\_L$

(a) Suppose $L$ is a language and $I(L)$ is finite. Construct a DFA recognizing $L$ that has exactly $I(L)$ states.

(b) Consider the language $L = \\{www : w \in \\{a,b\\}^\*\\}$. Show that $L$ is not regular by giving infinitely many pairwise inequivalent elements. \[which is something proven to work earlier\]

---

Now, for (a) I think I got a reasonable solution, for (b) I don't feel so sure.

For part (a) I describe an algorithm which first creates a start state for the DFA and labels it $\bar\varepsilon$, i.e. the $\equiv\_L$-equivalence class of $\varepsilon$. Second, for each letter $a$ in the input alphabet a new state $\bar a$ is created and a transition from $\bar\varepsilon$ to $\bar a$ is labelled $a$. Then all the states with the same label are merged in a single state, and the transitions are adjusted as a consequence. Hence, this procedure just carried on $\bar\varepsilon$ is iterated to each state just added. The algorithm stops when an iteration does not add any new state or transition.

Do you think that the writer wanted me to use this much information about $\equiv\_L$-equivalence classes or there is a neater solution?

For part (b), I believe that all the words generated by $ab^\*$ are pairwise not $\equiv\_L$-equivalent, with that $L$. Am I not sure I can justify it further than this, but is there another simpler example?

Thank you for any help, this is a rather long question.

# Answer
(a) Let $\Sigma$ be the alphabet of $L$ and $\Sigma^\*/\equiv\_L$ the set of equivalence classes of words over $\Sigma$ according to the equivalence relation $\equiv\_L$. Define the DFA to have one state for each element of $\Sigma^\*/\equiv\_L$ (we could think of the states as the classes themselves). Define the initial state to be the class of the empty word $\epsilon$, the accepting states to be the classes of the words in $L$. For each pair of states $s\_1,s\_2\in \Sigma^\*/\equiv\_L$ and letter $t\in\Sigma$ we will have the value of the transition function $\delta(s\_1,t)=s\_2$ if and only if for a word (equivalently, for all words) $x\in s\_1$ we have that the word $xt\in s\_2$.

(b) The examples that you showed work. The classes of the words $ab^n$, for $n=1,2,...$ are all different. In fact, if $x=ab^m$, $y=ab^n$ and $m\>n$, then taking $w=ab^nab^n$ we get that $xw\not\in L$, while $yw\in L$. Therefore, $x\not\equiv\_L y$.
> 0 votes

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


# Question
Title: Clarification on an Hopcroft book DFA minimization example
At page 156 there is an example on how to find the distinguishable states for the following automaton:

The following table shows the distinguishable states:

By applying the given definition for distinguishable states, it is not clear why E and G are considered distinguishable. For my understanding there is at least one string, "110" for example, that make them distinguishable, but one cannot test all the possible strings. I'm sorry if my question sounds dumb but I'm a beginner for this topic.

# Answer
It looks like you missed the paragraph for induction right before the Example 4.19 or figure 4.9 and the repetitive application of that induction.

> **INDUCTION**: Let $p$ and $q$ be states such that for some input symbol $a,$ $\ r =\delta(p,a)$ and $s = \delta(q,a)$ are a pair of states known to be distinguishable. Then $\\{p, q\\}$ is a pair of distinguishable states.

That induction is all we employ to fill the table of state inequivalences besides the fact that every accepting state is distinguishable from every non-accepting state. (The fact holds because the empty string distinguishes them.) That is, we will never check strings that are more than one symbol long.

For example, to find whether $E$ and $G$ are distinguishable, we need to just check either $0$ or $1$ distinguishes them. Assuming $E$ and $F$ are distinguishable, since on input $1$, $E$ go to $F$, while $G$ goes to $E$, we know $E$ and $G$ are distinguishable.

You might ask, how do we know $E$ and $F$ are distinguishable? By the same procedure. "Since $\\{C, H\\}$ is distinguishable, and states $E$ and $F$ go to $H$ and $C$, respectively, on input $0$".

Note that we may not be able to determine whether $E$ and $G$ are distinguishable right from the start by this procedure. We will try the pair $\\{E,G\\}$ again and again together with other pairs until we cannot find more distinguishable pairs. Although we may have to check the same pair for many times, the number of times is bounded by the number of distinguishable pairs and each time we will check just 2 possible distinguishing strings, $0$ and $1$. We have avoided testing "all the possible strings", which are infinite.

You may want to look at another explanation of Hopcroft's algorithm such as this Wikipedia article or the excellent illustration at tutorialspoint.
> 1 votes

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


title: Ramifications of P?NP Being Undecidable

text:
# Question
Title: Ramifications of P?NP Being Undecidable
Godel proved there are true statements in arithmetic that can't be proven true in any sufficiently strong Formal Axiomatic System (FAS). The authors of this paper use similar arguments to prove there are TM's that belong to a certain complexity class that cannot be proven to belong to that class. They refer to these type of algorithms as "hidden machines".

ON THE EXISTENCE OF HIDDEN MACHINES IN COMPUTATIONAL TIME HIERARCHIES

What happens to the quesion of P?NP if there exists a TM that can solve any satisfiable 3SAT instance in polynomial steps, yet, it is impossible to prove this TM does so?

# Answer
In some sense, nothing much. We still have P = NP. It's possible for there to be statements that are true even though we can't prove them true.

In another sense, something interesting happens: in your scenario, we can explicitly write down a new algorithm that is guaranteed to solve 3SAT in polynomial time, using Levin universal search. See https://cs.stackexchange.com/a/92095/755. So, if there is a non-constructive proof that 3SAT is in P, then you can find a constructive proof that 3SAT is in P.

See also Is P decidable?, Assuming P = NP, how would one solve the graph coloring problem in polynomial time?, Explicit algorithms and algorithms involving unknowns.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Find a maximum matching that saturates a given set of vertices
In an unweighted bipartite graph $G = (X + Y,E)$, we would like to find a maximum matching, but among all those maximum matchings, we would like to find one that saturates a given subset $X\_0\subseteq X$.

A necessary condition for the existence of such a matching is that $X\_0$ satisfies Hall's marriage condition, i.e., for every $X'\subseteq X\_0$, the number of neighbors of $X'$ is at least $|X'|$. If this condition is satisfied, we can find a matching $M$ that saturates all vertices of $X\_0$, but $M$ is not necessarily a maximum matching in $G$.

Is it always possible to extend $M$ into a maximum matching? Alternatively, is there a different way to find a maximum matching that saturates $X\_0$ when the necessary condition is satisfied?

# Answer
After some research, I found out that my question is a special case of the problem of priority matching. In this case there are two priority classes, $X\_0$ and $X\_1 := V\setminus X\_0$. The goal is to find a matching that maximizes the number of saturated vertices in $X\_0$, and subject to that, the number of saturated vertices in $X\_1$. There are efficient algorithms that solve this problem for any number of priority classes. It is known that any priority matching is also a maximum-cardinality matching.
> 6 votes

---
Tags: graphs, bipartite-matching
---


# Question
Title: Does canonicity imply weak normalization?
Context: type theory.

My understanding of:

* WN: every term can rewrite to NF.
* Canonicity: every term rewrites into canonical form.

Then it leads to an intuition where if canonicity holds, then we get NF = canonical form and therefore WN holds. However, I don't see people state this often, like this question talks about canonicity but never mentions NF or normalization. On nLab, canonical form is said to be normal form, which justifies my "NF = canonical form" guess but it doesn't say WN therefore holds. Therefore I'm doubting my intuition.

So, I wonder if it's right (is there a proof?), or if it's wrong (is there a counterexample?).

# Answer
> 7 votes
Canonicity does not imply weak normalization. First, let me phrase the involved definitions more precisely:

* WN: every open term is reducible to a normal term
* Canonicity: every closed term is reducible to a canonical term

(Note: in modern metatheory of type theory, it is more common to talk about conversion instead of reduction, and likewise to talk about unique existence of normal forms instead of weak/strong normalization. This answer remains valid if we replace "reducible" above with "convertible").

Normal and canonical terms are not the same. For example, the `x` variable in `x : Bool` context is normal but not canonical. Also, the closed term `λ(b : Bool). if true then b else b` is canonical but not normal.

Extensional type theory has the canonicity property but not WN, SN, or unique existence of normal forms. That's because in ETT it is possible to add an inconsistent definitional equality to the context, or add an equational theory of a Turing-complete system. For example, in the ETT context `n : Nat, p : n = suc n` the `n` variable has no unique normal form, since `n` can be expanded arbitrarily using `p`.

However, if we have a closed ETT term, we can't have anything dodgy in the context, so a closed term can be still evaluated to a canonical form.

---
Tags: type-theory
---


title: Maximum one-to-many matching

text:
# Question
Title: Maximum one-to-many matching
Let $G = (X+Y,E)$ be a bipartite graph and $k\geq 1$ an integer. A **maximum $k$-matching** is a subset of $E$ in which each vertex of $X$ is adjacent to at most $k$ edges and each vertex of $Y$ is adjacent to at most $1$ edge.

A maximum-cardinality $k$-matching can be found by the following algorithm:

* Create $k$ copies of each vertex $x\in X$, such that each copy is adjacent to all neighbors of $x$ in $Y$.
* Find a maximum matching in the resulting graph.

Its run-time complexity for a graph with $n$ vertices and $m$ edges, using the Hopcroft-Karp algorithm, is $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.

I am interested in the following alternative algorithm:

* Repeat $k$ times:

+ Find a maximum matching in $G$.
    + Remove the matched vertices of $Y$ from the graph.

Its run-time complexity is $O(k \cdot m\sqrt{n})$.

But does this algorithm always find a maximum $k$-matching?

# Answer
No. Here is a counterexample: $X=\\{a,b\\}, Y=\\{c,d,e,f\\}, E=\\{ac, ad, ae, be, bf\\}, k=2$. The first iteration of your algorithm could choose $\\{ae,bf\\}$ (in particular, the edge $ae$), preventing a solution from being found even though one does exist: $\\{ac, ad, be, bf\\}$.
> 2 votes

---
Tags: matching, bipartite-graph
---


# Question
Title: Really confused about latency with pipelining
I finished watching a video about pipelining https://www.youtube.com/watch?v=eVRdfl4zxfI which I thought made sense. Latency is the amount of time it takes to complete each instruction. Even with pipelining, the time it takes to complete an instruction is still the sum of the time it takes for every stage, in this case it's 20ns.

But then I did a bit more studying and found out the latency is supposed to be time for the longest stage to finish execution + the "cost" of pipelining, rather than the sum of time it takes to execute all the stages? http://web.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/perform.html

Is there something I'm missing?

# Answer
> 1 votes
In practice, you won't find any processor where different pipeline stages take different amounts of time - that would be a nightmare to implement. In practice, every pipeline stage takes one clock cycle.

"Latency" is the time from the start of the instruction to the point where the result can be used. For example, it takes some time from starting execution of an instruction x = y * z until an instruction a = b + x can start, because the result of the first instruction must first be available. That is *not* necessarily the execution time of the first instruction. There may be additional time needed to move the result of the multiplication into the register x, if the processor is clever enough in a = b + x to use the result of the multiplier as soon as it is available, instead of insisting on reading the register x.

Latency is important when you have a long sequence of instructions where each is dependent of the result of the previous one, and you don't have any other instructions that can be executed at the same time.

# Answer
> 0 votes
It is possible that you did not understand the mentioned references. Let say that $T\_s$ is the time that is needed for completion of each stage, and $k$ is the number of stages. $T\_s$ may or may not include the cost of pipelining. The latency of the first instruction is equal to the sum of times needed for completion of each stage, i.e., $kT\_s$. Once the pipeline is full, the latency of each subsequent instruction is $T\_s$. Therefore, the total time needed for execution of $n$ instructions is: $kT\_s$ (first instruction) $+ (n - 1) T\_s$ (each subsequent instruction).

Therefore, when pipeline is full, latency of each instruction is $T\_s$. Still, the time needed for completion of each instruction is $kT\_s$. Please note the difference between the latency and the time needed for completion of instruction. Pipelining only reduces the latency.

---
Tags: computer-architecture
---


# Question
Title: Show that the inequality holds for all positive integers
$a\_1=2,a\_2=9,a\_n=2a\_{n-1}+3a\_{n-2}$ for $n\>=3$

## Show $a\_n\<3^n$ for all positive integers n

## Base case: $a\_3 = 2\*9+3\*2 = 24\<=3^3$ is true

## Hypothesis: $a\_k\<=3^k$ for $k\epsilon\mathbb{N}$, show $a\_{k+1}\<=3^{k+1}$

Begin:

$a\_k\<=3^k$ implies $3a\_k\<=3^{k+1}$

by definition: $a\_{k+1} = 2a\_k+3a\_{k-1}$

$2a\_k + 3a\_{k-1} \<= 2a\_k + a\_k = 3a\_k \<= 3^{k+1}$

Because $3a\_{k-1} = 2a\_{k-1} + a\_{k-1} = 2a\_{k-1}+2a\_{k-2}+3a\_{k-3}$

$3a\_{k-1}$ will always be smaller than $a\_k$ because $2a\_{k-2}+3a\_{k-3}$ is always smaller than $3a\_{k-2}$

So because $a\_{k+1} \<= 3a\_k$ and $3a\_k\<=3^{k+1}$ then $a\_{k+1}\<=3^{k+1}$ which proves $a\_n\<=3^n$ for all n

Is my proof legit?

# Answer
> 0 votes
We are not going to prove that $a\_k\geq 3a\_{k-1}$ because it is not true: $$a\_3=2a\_2+3a\_1=2\cdot 9+3\cdot 2=24\<3\cdot 9=3a\_2$$

---

We also don't have $a\_k\<3^k$ for all $k$, since $a\_2=9=3^2$. That's probably a typo.

---

Let's prove, by induction, that for all natural $k$ we have $a\_k\leq 3^k$.

We have that $a\_1=2\leq 3=3^1$.

Assume that $a\_{k-2}\leq 3^{k-2}$ and $a\_{k-1}\leq 3^{k-1}$. Or you can assume that $a\_t\leq 3^t$ for all $t\<k$.

Then $$\begin{align} a\_k&=2a\_{k-1}+3a\_{k-2}\\ &\leq 2\cdot 3^{k-1}+3\cdot 3^{k-2}\\ &=3\cdot 3^{k-1}\\ &=3^{k} \end{align}$$

Therefore, $a\_{k}\leq 3^{k}$.

By induction, for all natural $k$ we have that $a\_{k}\leq 3^k$.

---
Tags: recurrence-relation, recursion, equality
---


# Question
Title: Proof of Simple Properties About Terms, Position of Subterms and Replacement of Subterms
I am studying term rewriting by reading Baader/Nipkow's book: "Term Rewriting and All That".

I want to prove a lemma about terms, position of subterms and replacement of subterms. The notation is as follows:

> $s|\_{p}$ denotes the subterm of $s$ at position $p$.
> $s\[t\]\_{p}$ denotes the term obtained from $s$ by replacing the subterm at position $p$ by $t$.

The lemma I want to prove is:

> **Lemma 3.1.4** Let $s, t, r$ be terms and $p, q$ be strings over the positive integers.
>
> 1. If $pq \in Pos(s)$, then $s|\_{pq} = (s|\_{p})|\_{q}$.
> 2. If $p \in Pos(s)$ and $q \in Pos(t)$, then
>
> 2.1 $(s\[t\]\_{p})|\_{pq} = t|\_{q}$
>
> 2.2 $(s\[t\]\_{p})\[r\]\_{pq} = s\[t\[r\]\_{q}\]\_{p}$
> 3. If $pq \in Pos(s)$, then
>
> 3.1 $(s\[t\]\_{pq})|\_{p} = (s|\_{p})\[t\]\_{q}$
>
> 3.2 $(s\[t\]\_{pq})\[r\]\_{p} = s\[r\]\_{p}$.
> 4. If $p$ and $q$ are parallel positions in $s$ (i.e. $p || q$), then
>
> 4.1 $(s\[t\]\_{p})|\_{q} = s|\_{q}$
>
> 4.2 $(s\[t\]\_{p})\[r\]\_{q} = (s\[r\]\_{q})\[t\]\_{p}$

The book provides proof for the first item:

> As an example, we show, by induction on the length of $p$ that $s|\_{pq} = (s|\_{p})|\_{q}$ holds for all $pq \in Pos(s)$.
>
> For $p = \epsilon$, we have $pq = q$, and thus $s|\_{pq} = s|\_{q}$. In addition, $p = \epsilon$ implies $s|\_{p} = s$, which shows $s|\_{q} = (s|\_{p})|\_{q}$.
>
> Now assume that $p = ip'$. Because $ip'q \in Pos(S)$, we know that $s$ is of the form $s = f(s\_1, \ldots, s\_n)$ with $i \leq n$. By definition, $s|\_{pq} = s|\_{ip'q} = s\_{i}|\_{p'q}$, and by induction $s\_{i}|\_{p'q} = (s\_{i}|\_{p'})|\_{q}$. Again, by definition, we obtain $s\_{i}|\_{p'} = s|\_{ip'} = s|\_{p}$, which finishes the proof of the induction step.

I want to prove that the other items are also true. I wrote my attempt as an answer, but of course, I welcome other solutions or feedback. Thanks in advance.

# Answer
**Item 2. If $p \in Pos(s)$ and $q \in Pos(t)$:**

**2.1 $(s\[t\]\_{p})|\_{pq} = t|\_{q}$.**
We prove by induction on the length of $p$:

**Case $p = \epsilon$:**
$(s\[t\]\_{\epsilon})|\_{\epsilon q} = t|\_{\epsilon q} = t|\_{q}$.

**Case $p = ip'$:**
$(s\[t\]\_{ip'})|\_{ip'q} = f(s\_1, \ldots, s\_i\[t\]\_{p'}, \ldots, s\_n)|\_{ip'q} = (s\_{i}\[t\]\_{p'})|\_{p'q}$. By induction hypothesis, $(s\_{i}\[t\]\_{p'})|\_{p'q} = t|\_{q}$.

**2.2 $(s\[t\]\_{p})\[r\]\_{pq} = s\[t\[r\]\_{q}\]\_{p}$.**
We prove by induction on the length of $p$:

**Case $p = \epsilon$:**
Notice that $(s\[t\]\_{\epsilon})\[r\]\_{\epsilon q} = t\[r\]\_{q}$ and also that: $s\[t\[r\]\_{q}\]\_{\epsilon} = t\[r\]\_{q}$.

**Case $p = ip'$:**
$(s\[t\]\_{ip'})\[r\]\_{ip'q} = f(s\_1, \ldots, s\_{i}\[t\]\_{p'}, \ldots, s\_n)\[r\]\_{ip'q} = f(s\_1, \ldots, (s\_{i}\[t\]\_{p'})\[r\]\_{p'q}, \ldots, s\_n)$. By induction hypothesis, $$(s\_{i}\[t\]\_{p'})\[r\]\_{p'q} = s\_i\[t\[r\]\_{q}\]\_{p'}$$ and hence $f(s\_1, \ldots, (s\_{i}\[t\]\_{p'})\[r\]\_{p'q}, \ldots, s\_n) = f(s\_1, \ldots, s\_i\[t\[r\]\_{q}\]\_{p'}, \ldots, s\_n) = s\[t\[r\]\_{q}\]\_{ip'}$.

**Item 3. If $pq \in Pos(s)$, then :**

**3.1 $(s\[t\]\_{pq})|\_{p} = (s|\_{p})\[t\]\_{q}$.**
We prove by induction on the length of $p$:

**Case $p = \epsilon$:**
notice that $(s\[t\]\_{\epsilon q})|\_{\epsilon} = s\[t\]\_{q}$ and also that $(s|\_{\epsilon})\[t\]\_{q} = s\[t\]\_{q}$.

**Case $p = ip'$:**
$(s\[t\]\_{ip'q})|\_{ip'} = f(s\_1, \ldots, s\_{i}\[t\]\_{p'q}, \ldots, s\_n)|\_{ip'} = (s\_{i}\[t\]\_{p'q})|\_{p'}$. By induction hypothesis:

$$(s\_{i}\[t\]\_{p'q})|\_{p'} = (s\_{i}|\_{p'})\[t\]\_{q}$$

But $(s|\_{ip'})\[t\]\_{q} = (s\_{i}|\_{p'})\[t\]\_{q}$ and thus the result holds.

**3.2 $(s\[t\]\_{pq})\[r\]\_{p} = s\[r\]\_{p}$.**
We prove by induction on the length of $p$:

**Case $p = \epsilon$:**
$(s\[t\]\_{\epsilon q})\[r\]\_{\epsilon} = r = s\[r\]\_{\epsilon}$.

**Case $p = ip'$:**
$(s\[t\]\_{ip'q})\[r\]\_{ip'} = f(s\_1, \ldots, s\_{i}\[t\]\_{p'q}, \ldots, s\_n)\[r\]\_{ip'q} = f(s\_1, \ldots, (s\_{i}\[t\]\_{p'q})\[r\]\_{p'}, \ldots, s\_n)$. By induction hypothesis:

$$(s\_{i}\[t\]\_{p'q})\[r\]\_{p'} = s\_{i}\[r\]\_{p'} $$

and therefore we have $f(s\_1, \ldots, (s\_{i}\[t\]\_{p'q})\[r\]\_{p'}, \ldots, s\_n) = f(s\_1, \ldots, s\_{i}\[r\]\_{p'}, \ldots, s\_n) = s\[r\]\_{ip'}$.

**Item 4. If $p$ and $q$ are parallel positions in $s$ (i.e. $p || q$), then**

**4.1 $(s\[t\]\_{p})|\_{q} = s|\_{q}$**
We prove by induction on the length of $p$:

**Case $p = \epsilon$:** This case can't happen, as $p$ and $q$ would not be parallel positions.

**Case $ p = ip'$:**
We now prove this by induction on the length of $q$.
If $q = \epsilon$:

> This can't happen, as $p$ and $q$ would not be parallel positions.

If $q = jq'$:

> There are two possibilities, according to whether $i = j$ or not.
> **Case $i = j$:**
>
> > $(s\[t\]\_{ip'})|\_{iq'} = f(s\_1, \ldots, s\_{i}\[t\]\_{p'}, \ldots, s\_{n})|\_{iq'} = (s\_{i}\[t\]\_{p'})|\_{q'}$. We have that $p'$ and $q'$ are parallel positions and thus, by induction hypothesis: $$(s\_{i}\[t\]\_{p'})|\_{q'} = s\_{i}|\_{q'}.$$ Since we also have $s|\_{iq'} = s\_{i}|\_{q'}$ the result holds.
>
> **Case $i \neq j$:**
>
> > Let's suppose without loss of generality that $i \> j$. Then:
> > $$(s\[t\]\_{ip'})|\_{jq'} = f(s\_1, \ldots, s\_{j}, \ldots, s\_{i}\[t\]\_{p'}, \ldots, s\_{n})|\_{jq'} = s\_{j}|\_{q'}.$$ Since we also have $s|\_{jq'} = s\_{j}|\_{q'}$ the result holds.

**4.2 $(s\[t\]\_{p})\[r\]\_{q} = (s\[r\]\_{q})\[t\]\_{p}$**:

**Case $p = \epsilon$:** This case can't happen, as $p$ and $q$ would not be parallel positions.

**Case $ p = ip'$:**
We now prove this by induction on the length of $q$.
If $q = \epsilon$:

> This can't happen, as $p$ and $q$ would not be parallel positions.

If $q = jq'$:

> There are two possibilities, according to whether $i = j$ or not.
> **Case $i = j$:**
>
> > $(s\[t\]\_{ip'})\[r\]\_{iq'} = f(s\_1, \ldots, s\_{i}\[t\]\_{p'}, \ldots, s\_n)\[r\]\_{iq'} = f(s\_1, \ldots, (s\_{i}\[t\]\_{p'})\[r\]\_{q'}, \ldots, s\_n)$.
> > We have that $p'$ and $q'$ are parallel positions and thus, by induction hypothesis: $$ (s\_{i}\[t\]\_{p'})\[r\]\_{q'} = (s\_{i}\[r\]\_{q'})\[t\]\_{p'} $$ and hence $$f(s\_1, \ldots, (s\_{i}\[t\]\_{p'})\[r\]\_{q'}, \ldots, s\_n) = f(s\_1, \ldots, (s\_{i}\[r\]\_{q'})\[t\]\_{p'} , \ldots, s\_n)= f(s\_1, \ldots, s\_{i}\[r\]\_{q'}, \ldots, s\_n)\[t\]\_{ip'} = (s\[r\]\_{q})\[t\]\_{p}.$$
>
> **Case $i \neq j$:**
>
> > Let's suppose without loss of generality that $i \> j$. Then:
> > $$(s\[t\]\_{ip'})\[r\]\_{jq'} = f(s\_1, \ldots, s\_{j}, \ldots, s\_{i}\[t\]\_{p'}, \ldots, s\_n)\[r\]\_{jq'} = f(s\_1, \ldots, s\_{j}\[r\]\_{q'}, \ldots, s\_{i}\[t\]\_{p'}, \ldots, s\_n) = f(s\_1, \ldots, s\_{j}\[r\]\_{q'}, \ldots, s\_{i}, \ldots, s\_n)\[t\]\_{ip'} = (s\[r\]\_{jq'})\[t\]\_{ip'}.$$
> 0 votes

---
Tags: term-rewriting
---


# Question
Title: Functor in category theory: The free theorem for fmap
According to nLab article:

https://ncatlab.org/nlab/show/functor

---

## Definition

### External definition

A **functor** $F$ from a **category** $C$ to a category $D$ is a map sending each **object** $x \in C$ to an object $F(x) \in D$ and each **morphism** $f : x \to y$ in $C$ to morphism $F(f) : F(x) \to F(y)$ in $D$, such that

* $F$ preserves **composition**: $F(g\circ f) = F(g)\circ F(f)$ whenever the left-hand side is well-defined,
* $F$ preserves **identity morphisms**: for each object $x \in C$, $F(1\_x) = 1\_{F(x)}$.

---

So, functor is often called "structure preserving".

However, there is an interesting article:

https://www.schoolofhaskell.com/user/edwardk/snippets/fmap

---

## The free theorem for fmap

When we write down the definition of Functor we carefully state two laws:

1. `fmap id = id`
2. `fmap f . fmap g = fmap (f . g)`

These are pretty well known in the Haskell community.

What is less well known is that the second actually follows from the first and parametricity, so you only need to sit down and prove one `Functor` law when you go to supply a `Functor`!

This is a “folklore” result, which I've used in conversation many times before, but it continues to surprise folks, so I decided to write up a slow, step by step proof of this result as it is a fun little exercise in equational reasoning.

To prove this we're going to need the free theorem for `fmap` and a few lemmas.

---

So, my question is does this apply not only to the **category of set and function composition** but also **category theory in general**?

Thanks.

# Answer
Composition following from identity does not hold for the category of sets and functions (to my knowledge), if by that you mean the sets and functions in ZF(C) or the like that mathematicians usually consider. As you mentioned, the given argument relies on parametricity, and the functions definable in set theory needn't be parametric. In fact, assuming that all functions are parametric is anti-classical. Even in constructive scenarios which could admit parametric models, people might want to keep their options open.

It's probably not a huge surprise in light of the above, but things aren't going to work out in a lot of other situations, either. For instance, the argument you referenced is essentially appealing to parametricity to obtain naturality, because parametricity is a stronger requirement than naturality (based on a notion that doesn't involve composition). However, Haskell functions (or those of similar systems) are parametric with respect to a specific sort of "logical relation" that subsumes naturality with respect to a specific category. This parametricity does not automatically imply naturality even with respect to certain related categories. For instance, if you consider functors $\mathsf F, \mathsf G : \mathsf{Type}\_M → \mathsf{Type}$ from a Kleisli category, then a parametric function with type $∀ a. \mathsf F(a) → \mathsf G(a)$ is not automatically natural. So, there are examples like this where functoriality doesn't automatically follow just from the identity rule.

For instance, consider the Kleisli category for lists. There is a functor:

$$\mathsf F : \mathsf{Type}\_{\mathsf{List}} → \mathsf{Type}$$ $$\mathsf F\ A = \mathsf{List}\ A$$

where the action of $\mathsf F$ on arrows is given by the following code:

```
-- drops one element of the list unless it has only one element
contract : List A → List A
contract (_ :: xs@(_ :: _)) = xs
contract xs = xs

mapF : (A → List B) → List A → List B
mapF f [] = []
mapF f (x :: xs) = contract (f x) ++ mapF f xs

```

This action on arrows doesn't satisfy the composition rule, but it does satisfy the identity rule. There is a functorial action for this object mapping (it is the 'bind' operation), but `mapF` is another function with the same type and behavior on the Kleisli identity arrow (`pure` or `return` in Haskell).

I would imagine that composition following from identity is the exception rather than the rule.
> 1 votes

---
Tags: category-theory, haskell
---


# Question
Title: Booth's algorithm Question : Binary Number Arithmetic (Multiplication)
It's being said booth's algorithm produces the output exactly as normal binary multiplication while reducing the number of operations performed and can be used for both positive and negative numbers !

I tried multiplying two 4-bit numbers while I don't get the same result...Please guide what am doing wrong.

Multiplicand : **1101** , Multiplier : **1110**,
Recorded Multiplier(Applying skipping over 1's) : **00-10**

The Result's are different Please Help !

# Answer
> 1 votes
When you use normal multiplication, multiplicand and multiplier are represented using (Sign + Magnitude) representation. So effectively 1101 is +(13) in Decimal and (1110) is +14 in decimal as they represent the magnitude. Sign bit would be separate. So the result is (+13)\*(+14) = +182 which is 1011 0110 in binary.

When you use booth multiplication, operand are in 2's complement representation. So 1101 is -3 and 1110 is -2 in decimal. So the answer will be 0000 0110 that is +6 in decimal. The problem is with your representation of multiplicand and multiplier.

---
Tags: computer-architecture, arithmetic, multiplication
---


# Question
Title: Conversion of fractional part of a hexadecimal number to binary
The Number is given as : (C012.25)Hexadecimal I have to convert it into octal . So I converted it into Binary First and got the result as : **1100000000010010.01000000** *(Since each bit in hexadecimal represents 4 bit in binary so C=1100,0=0000,1=0001,2=0010 and for 0.25=.01000000 )* The Solution mentions the Binary conversion as **1100000000010010.00100101**

Please guide me about the what was done wrong ! Also if I got the binary representation...How can I convert the binary no's fractional part (0.00100101) into octal .

# Answer
Here is how to convert the fractional part from hexadecimal to binary: $$ (0.25)\_{16} = \frac{2}{16} + \frac{5}{16^2} = \frac{0 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1}{16} + \frac{0 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1}{16^2} = \\ \frac{0}{2} + \frac{0}{4} + \frac{1}{8} + \frac{0}{16} + \frac{0}{32} + \frac{1}{64} + \frac{0}{128} + \frac{1}{256} = (0.00100101)\_2 $$ As you can see, we simply replace $2$ with its base 2 representation, and then adjoin the base 2 representation of $5$. I included this calculation to show *why* this works.

Note also that $(0.25)\_{16} \neq 1/4$.
> 1 votes

---
Tags: arithmetic, binary, base-conversion
---


# Question
Title: Proof of lemma for flow in residual graph
In CLRS 3'rd edition there is a Lemma 26.2 which states that:

> Let $G=(V, E)$ be a flow network, let $f$ be a flow in $G,$ and let $p$ be an augmenting path in $G\_{f}$. Define a function $f\_{p}\colon V \times V \rightarrow \mathbb{R}$ by $$f\_{p}(u, v)=\left\\{\begin{array}{ll}c\_{f}(p) & \text { if }(u, v) \text { is on } p \\ 0 & \text { otherwise }\end{array}\right.$$ Then, $f\_{p}$ is a flow in $G\_{f}$ with value $\left|f\_{p}\right|=c\_{f}(p)\>0$

How would you go about proving this?

As I understand we need to check for flow conservation and capacity constraint. We know that $c\_f(p)$ is the minimum of the residual capacities on path $p$ which is smaller than the capacities, hence the capacity constraint is satisfied. But how about the flow conservation constraint and proving that the flow value is in fact $c\_f(p) \> 0$?

# Answer
> 2 votes
Observe that if $v$ is not a vertex of $p$, then $f\_p(u,v)=0$. When $v$ is in $p$ and not a source nor a sink, then there are only two vertices $v\_1$ and $v\_2$ such that the edges $(v\_1,v),(v,v\_2)$ are in $p$. Therefore, in the excess flow at $v$ $$\sum\_u f\_p(u,v)$$ only has two non-zero terms $f\_p(v\_1,v)=c\_f(p)$ and $f\_p(v\_2,v)=-f\_p(v,v\_2)=-c\_f(p)$.

So, the excess flow is zero.

To see that $c\_f(p)\>0$ just recall that it is defined as the minimum of the residual capacities of the edges of $p$. There are finitely many edges in $p$ and by definition of augmenting path the residual capacities of its edges are positive. So, you are taking the minimum of finitely many positive numbers. That results in a positive number.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Determine if there is a subset of the given set with sum divisible by a given integer
I've been given a question to solve:

> Given a set of non-negative distinct integers, and a value $m$, determine if there is a subset of the given set with sum divisible by $m$.

For this question the answer is here

I don't understand the part after `if DP[j]==True`
what is actually the intuition behind this code. Please explain in detail.

# Answer
Let f (i, k) = true if and only of there is a subset of the first k integers with a sum equal to i modulo m. As an example, if a\[12\] = 75, then f (i, 12) is true if and only if either f (i, 11) is true or f ((i-75) modulo m, 11) is true. And obviously f (i, 0) is true if and only if i = 0.

So if you have n integers, create a two dimensional array of size m * (n + 1), then fill array \[i, 0\] for all i, then fill array a \[i, 1\] for all i, and so on until you filled a \[i, n\] for all i. And there you have the solution.

Next you figure out how to do this without using an array of (n+1) * m elements, and you figure out when you can stop early because you know the answer already.

And I would be curious if there is any reason why these numbers would have to be a set.
> 1 votes

---
Tags: time-complexity, dynamic-programming
---


# Question
Title: Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?
The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the title, please tell me in your answer then I will try to make the title much clearer.

Suppose we have a list of integers $x\_1, x\_2,\ldots,x\_n$, what we want to find is the **smallest integer $y$** such that all the given integers can be found through the process of dividing $y$ by 2 (**on the division tree**). More specifically, the results of dividing $y$ by 2 are 2 integers: $⌊y/2⌋$ and $⌈y/2⌉$.

Example: for integers 1, 1 and 3, it is easy to prove that the lower bound of y is the sum of them, 5. As for 5, we can get all the integers we want by dividing itself: dividing 5 we get 2 and 3, where 3 is an integer we want; dividing 2 we get 1 and 1, all of which are expected results. Therefore, all the integers we want can be found in the process, 5 is the smallest integer $y$ we want.

Another example: for integers 2, 2 and 6, the lower bound of y is 2+2+6=10, but 10 is not a suitable candidate for y since 10÷2=5\<6, it cannot generate 6 in the process. However, if we plus 1, then 11 is the dream y we want. An illustrational graph is shown in the link:

**Notice that once we get an integer we want on the division tree (i.e. for the 2nd example above, get 6 in a branch of 11), we should accept it as a part of the result, stop dividing it and concentrate on results on the other branch. There also could be some redundant integers generated (i.e. 1 for the 2nd example above), and we just leave them alone.**

In all examples above, the smallest integer $y$ is found by trials, not a systematical algorithm. I just cannot come out with an algorithm to find $y$ systematically, and my question is how to **find the algorithm**.

# Answer
> 2 votes
$x\_1=5, x\_2=7$ is the smallest example where there is no common ancestor. Any ancestor of $x\_1$ is in the range $2 \cdot 2^k + 1 \le z \le 3 \cdot 2^k - 1$, any ancestor of $x\_2$ is in the range $3 \cdot 2^k + 1 \le z\le 4 \cdot 2^k - 1$. These are non-overlapping intervals with a gap of one number in between.

# Answer
> 0 votes
I think this is one way to do it:

1. Sort the list in ascending order (actually this can be omitted, but you should drop the 0s)
2. The first number becomes our candidate
3. Now we investigate the next number:
    1. Compare the candidate and the next number, the smaller one becomes x the bigger one becomes y
    2. Multiply x by 2 until the next multiplication would exceed y and count the number of multiplications, e.g. x = 2, y = 9 =\> result r = 8, multiplications m = 2
    3. If r + m \>= y then y becomes the candidate, continue with the next number
    4. d = 2 * r - y
    5. do the following calculation d times: y = 2 * y + 1
    6. y becomes the candidate and we continue with the next number

It is based on the idea that if you have a number n = m and calculate x times m = m * 2 + 1, then with m you can get all the numbers in the range from n to n + x.

---
Tags: algorithms, dynamic-programming, trees, binary-trees, recursion
---


# Question
Title: Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete?
MCG Problem: Consider a positive integer R and an undirected graph G = (V, E), in which each vertex is assigned a weight (or value). The maximum-weight connected graph (MCG) problem is to find a subgraph with R vertices that is connected and maximizes the sum of the weights (or values) of the R vertices.

CMCG Problem: The CMCG problem is the MCG problem with a constraint of having one predetermined (fixed) vertex included in the solution.

In  it has been stated (First paragraph, Section 1) that MCG is an NP-complete problem, which is proved in \[3\] (However I could not find the technical report \[3\] anywhere on the internet).

In  it has been "claimed" that CMCG is NP-complete (second to last paragraph, Section 3). But did not provide any proof.

I want to know (and see a proof, if possible) that if CMCG is NP-complete.

In  it has been shown that Steiner tree problem, which is NP-complete is a special case of the CMCG problem. Does it imply that CMCG is NP-complete?

\[3\]:Lee, H. F., and D. R. Dooly. The maximum-weight connected graph problem. Technical Report 93-4, Industrial Engineering, Southern Illinois University, 1993.

# Answer
> 1 votes
Firstly, note that you can reduce $CMCG$ to $MCG$ by setting the value of the node that must be in the set to the sum of all positive weights of all other nodes $+1$ and then applying $MCG$ and retrieving the result set. Thus $CMCG\in NP$.

As proved in the paper the $NP$-complete Steiner-Tree problem can be reduced to $CMCG$ meaning that $CMCG$ is $NP$-hard. If a problem is in $NP$ and $NP$-hard it is by definition $NP$-complete.

Hope this helps.

---
Tags: graphs, np-complete, weighted-graphs, subgraphs
---


# Question
Title: Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?
## Question

Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?

1. The adding a parameter is needed because a NP-hard problem is normally just a question with a yes or no answer, if you want to limit some parameter you need to specify which one (even though something like $k$-Coloring might have an obvious one already), so with "specifying which parameter" one is limiting, one is "adding a parameter" to the problem. A more detailed description is included in the answer by Discrete Lizard.
2. I think Natural tries to exclude "trivial" parameterizations as I discuss in my first doubt in this question. Again a more detailed description is included in the answer by Discrete Lizard.

## Doubt

0. It might be a trivial question as it perhaps is possible to always "stuff" the entire problem within the $f(k\_1,k\_2,..,k\_m)$ part of the $f(k\_1,k\_2,..,k\_m)n^c$ algorithm whilst setting $n=c'$ where $c'$ is an arbitrary constant. But perhaps the exact definition of FPT prevents such (ab)use of the concept of FPT.

Based on the comment of plop there indeed exists a trivial way to parameterize "any" (I assume any properly well-posed problem) problem, such that its parameterization is fpt. Those parameterizations use languages, which I assume to be what is described here. Such a "trivial" (in light of the question, not in light of difficulty) parameterization is intended to be ignored. So in the "words" of Discrete lizard: non-trivial parameter range(s) is(are) intended.

# Answer
You have to be a bit careful with your question here. Note that an NP-hard problem is a decision problem, while FPT algorithms solve *parametrized* decision or search problems. So the question is a bit poorly formed. However, I think the question you probably intended to ask is:

> Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?

To which the answer is (unconditionally!) **yes**.

First of all, note that FPT, the class of problems that are solvable via a fixed parameter tractable algorithm, is a proper subset of XP, the class of "slice-wise polynomial" parameterized problems that can be solved by a polynomial-time algorithm if the parameter is fixed. In other words: $\mathrm{FPT} \subsetneq \mathrm{XP}$. (The authors only claim the proof goes by "standard diagonalization". See this answer for a full proof. )

Next, note that since at least one problem in XP cannot be solved by an FPT-algorithm, any XP-hard (in the sense of FPT-reductions) problem cannot be solved by an FPT-algorithm.

In the chapter "Provable Intractability: The Class XP" in Downey and Fellows' *Fundamentals of Parameterized Complexity*, they complete the argument by showing that what they call the **PEBBLE GAME PROBLEM** is XP-hard by "reinterpreting" a problem that is known to be at least PSPACE-hard (after "removing the parameter"), so certainly NP-hard. See there book chapter for more details.

---

Let me add that this result was very surprising to me as well, because for most *practical* problems, we require al sorts of conjectures ($P\neq NP$, ETH, SETH, 3-SUM, etc.), but this result is an actual fact that is independent of any conjecture.

---

1: To clarify, by "adding a parameter", I mean given an NP-hard problem $L\subseteq \Sigma^\*$, define a parametrized problem $L'\subseteq \Sigma^\* \times \mathbb{N}$ as $L':= \\{\langle x, k\rangle \mid f(x)=k\\}$ for some function $f : \Sigma^\* \rightarrow \mathbb{N}$. This captures the intuitive idea that the additional parameter measures a property of the input.
2: The definition in 1 still allows all sorts of strange parameterizations with functions such as $f(x)\equiv 1$. Ideally, we'd require $f$ to measure something meaningful about the instance, but that seems hard to formalize. I couldn't think of any other formalisation that removes all "unnatural" parameterizations, either. So, I will instead copy the informal notion of "natural parameterized problems" from Downey and Fellows' book.
> 6 votes

# Answer
I would say yes, but you need to accept the condition that P $\neq$ NP. Take $k$-Coloring, where we want to determine whether a graph can be colored with $k$ colors such that any two connected vertices do not have the same color. Clearly, we can reduce 3-Coloring to $k$-coloring.

Suppose $k$-Coloring is in FPT, then there exists an algorithm that solves this problem in $f(k) \cdot n^{O(1)}$. If we set $k = 3$, then we obtain a polynomial-time algorithm, and thus 3-Coloring can be solved in polynomial-time unless P $\neq$ NP. Obviously, if P $\neq$ NP, then there is no FPT algorithm for $k$-Coloring.

If you are looking for something more strictly in the sense that it absolutely cannot exist, then I am not sure whether such a problem has been found.
> 3 votes

# Answer
Perhaps another option, significantly weaker than STanja's solution and Discrete lizards solution, is assuming the exponential time hypothesis (ETH). ETH assumes $FPT \neq W\[1\]$ (Or just assume FPT $\neq$ W\[1\] directly).

So with FPT $\neq$ W\[1\] one assumes no (non-trivial) parameterization $K-D$ of a W\[1\]-hard problem is FPT. An example of a w\[1\] hard problem that is NP-hard\* is $k-clique$, so there exists a w\[1\]-hard problem that is an NP-hard problem. Since (non-trivial) parameterization $K-D$ w\[1\]-hard problems are not (in) fpt with assumption FPT $\neq$ W\[1\], this means, any (non-trivial) parameterization $K-D$ of NP-hard problem $k-Clique$ is not FPT. That means, if FPT $\neq$ W\[1\], there exists a NP-hard problem that is not FPT.

* The decision problem ($k$)-clique is NP-complete, therefore, it is also NP-hard as the picture below shows:

## Disclaimer

I did not come up with this argument, it is basically the comment of Discrete lizard, and it is almost like answering the question: "does $a$ exist?" with: "I assume that $b$ exists, oh there happens to be an $a$ that is in set $b$, and since I assumed $b$ exists, then there must also exist an $a$, so yes there exists an $a$. (as is also explained by Discrete lizard in the comments)
> 0 votes

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


# Question
Title: Test two LTL expression trees for equivalence
Is there an algorithm on how to check if two LTL expressions (represented as binary trees) are semantically equivalent? Since there are many smaller equivalences such as $a\Rightarrow b \equiv \neg a \vee b$ or $F(a) \equiv true U a$ as well as commutativity, distributivity, etc. that need to be considered.
My initial idea was to create the truth table for both expressions and compare them. But then the temporal operators would not be taken into account. Creating and comparing the automaton for each expression sounds like it would be rather inefficient.

Is there a better way to do this?

# Answer
Unfortunately, the approach of constructing automata for each formula and testing their equivalence is pretty much the best you can do.

The problem of checking whether an LTL formula is valid, that is, whether it is satisfied in every computation, is PSPACE complete (this is an easy exercise, given that LTL satisfiability is PSPACE complete).

Thus, checking whether two LTL formulas are equivalent is also at least PSPACE hard, since you can reduce from the former by testing equivalence with the formula "true".

In order to show membership in PSPACE, you can take the standard approach of checking equivalence of the corresponding automata "on the fly", without actually constructing them explicitly.
> 3 votes

---
Tags: logic, binary-trees, linear-temporal-logic
---


# Question
Title: Not understanding this way of proving undecidability of the termination problem
I am reading some slides on Algorithm to understand why termination is an undecidable problem. The slides say the following:

– Assume termination(P) always terminates and returns true iff P always terminates on all input data;

– The following program yields a contradiction

```
while termination(P) skip;

```

But I do not see what kind of contradiction there. Any idea?

# Answer
> 3 votes
This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain this remarkable and beautiful argument, from many viewpoints.

Still, to answer your question: denote by $Q$ the program you describe. Then $Q$ is a valid program, that takes as input another program $P$, and works as above.

Now ask yourself - what would $Q$ do if you gave it its *own* encoding $Q$? Would it terminate or not?

* If $Q$ terminates when given $Q$, then the "while" condition would stay true, meaning $Q$ would not terminate when given $Q$, but this is a contradiction.
* If $Q$ does not terminate when given $Q$, then the while condition is false, so $Q$ does terminate when given $Q$, which is again a contradiction.

Therefore, a procedure such as "terminate" cannot exist.

Again, I cannot stress this enough -- read this proof elsewhere, watch youtubes of it, read textbooks. It's one of the most fundamental and exciting results in computer science!

---
Tags: undecidability, check-my-answer, termination
---


# Question
Title: Proving non-regularity via syntactic congruence classes?
Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation:

$$x \equiv\_M y \Leftrightarrow \forall v \in \Sigma^\*. (xv \in L \leftrightarrow yv \in L).$$

One corollary of the Myhill-Nerode theorem is that if $\equiv\_M$ has infinitely many equivalence classes, then $L$ is not a regular language.

There's a different equivalence relation called syntactic congruence which is also due to Myhill:

$$x \equiv\_S y \Leftrightarrow \forall u \in \Sigma^\*. \forall v \in \Sigma^\*. (uxv \in L \leftrightarrow uyv \in L).$$

My question is the following: is it also the case that if $\equiv\_S$ has infinitely many equivalence classes, then $L$ is not a regular language? I've tried a smattering of regular languages and each one I've tried has a finite number of these equivalence classes, but I don't see a way to get a general proof to that effect (and I'm not even sure one exists!)

# Answer
> 1 votes
After a bit more thought I believe this is indeed true and that I've got a proof of it. The idea is to proceed by contrapositive and instead prove that if $L$ is regular, then $\equiv\_S$ has only finitely many equivalence classes.

We can see this by pulling in Brzozowski derivatives. Given the language $L$ and any string $x \in \Sigma^\*$, we define the Brzozowski derivative of $L$ with respect to $x$ as

$$\partial\_x L = \\{ w \in \Sigma^\* | xw \in L \\}$$

With this notation, we see that $uxv \in L$ is equivalent to saying that $xv \in \partial\_u L$. This means that we can rewrite the definition of $\equiv\_S$ as

$$x \equiv\_S y \Leftrightarrow \forall u \in \Sigma^\*. \forall v \in \Sigma^\*. (xv \in \partial\_u L \leftrightarrow yv \in \partial\_u L).$$

But that inner part is the definition of Myhill congruence for the language $\partial\_u L$, which we'll denote as $\equiv\_{M({\partial\_u L})}$. Therefore, we see that

$$x \equiv\_S y \Leftrightarrow \forall u \in \Sigma^\*. x \equiv\_{M({\partial\_u L})} y$$

A few fun facts about Brzozowski derivatives:

1. For any language $L$ we have $x \equiv\_{M(L)} y$ if and only if $\partial\_x L = \partial\_y L$. This follows from the definitions - $xw \in L$ means the same as $w \in \partial\_x L$.
2. As a corollary, any regular language has a finite number of distinct Brzozowski derivatives.
3. The derivative of a regular language is regular - you can just change the start state to the state reached by $x$ to form a DFA for $\partial\_x L$ from a DFA for $L$.
4. As a corollary, $\equiv\_{M({\partial\_u L})}$ has only finitely many equivalence classes for any string $u$.

So overall, we see that $x \equiv\_S y$ means that $x$ and $y$ are Myhill-equivalent for each of the (finitely many) distinct Brzozowksi derivatives of the original language. There are only finitely many combinations of a derivative and a Myhill equivalence class of the derivative, so there are only finitely many equivalence classes for $\equiv\_S$.

There is almost certainly a better way to prove this, but this is just the one I came up with. Please let me know if I missed anything or if this is incorrect!

# Answer
> 2 votes
You want to prove that if $\equiv\_S$ has infinite index, then $L$ is not a regular language, or, equivalently that if $L$ is regular, then $\equiv\_S$ has finite index. This is an immediate consequence of the following result.

**Theorem**. Let ${\cal A} = (Q, \Sigma, \cdot, i, F)$ be the minimal complete deterministic automaton of $L$. Then $u \equiv\_S v$ if and only if, for every state $q \in Q$, $q \cdot u = q \cdot v$.

**Proof**. Suppose that $u \equiv\_S v$ and let $q \in Q$. Since $\cal A$ is minimal, it is accessible, and there exists a word $x$ such that $i \cdot x = q$. Now, for every word $y$, $$ xuy \in L \iff xvy \in L, $$ or, equivalently, $$ 1 \cdot xuy \in F \iff 1 \cdot xvy \in F $$ that is, $$ (q \cdot u) \cdot y \in F \iff (q \cdot v) \cdot y \in F $$ It follows that the states $q \cdot u$ and $q \cdot v$ are equivalent, and hence equal, since $\cal A$ is minimal.

Suppose now that for every state $q \in Q$, $q \cdot u = q \cdot v$. Let $x$ and $y$ be words. Then the following equivalences hold: \begin{align} xuy \in L &\iff 1 \cdot xuy \in F \iff ((1 \cdot x) \cdot u) \cdot y \in F \\ &\iff ((1 \cdot x) \cdot v) \cdot y \in F \iff 1 \cdot xvy \in F \\ &\iff xvy \in L \end{align} and thus $u \equiv\_S v$.

---
Tags: formal-languages, regular-languages
---


title: Need help to proof that NP⊆NP4

text:
# Question
Title: Need help to proof that NP⊆NP4
NP4 = { L | There exists a non deterministic polynomial Turing machine M, such that for every x∈L, M accepts x on at least 4 paths in the computational tree of M on x. and for every x∉L,M accepts x on at most 3 paths in the computational tree of M on x. }

# Answer
Take any language $L \in \mathsf{NP}$ and let $T$ be a non-deterministic polynomial-time Turing machine that decides $L$. Let $\Gamma$ and $q\_A$ be the tape alphabet and the accepting state of $T$, respecitvely.

Create a new Turing machine $T'$ that has the same states of $T$ plus four additional states $q\_1, q\_2, q\_3, q\_4$. $T'$ is obtained from $T$ by:

* Replacing each transition $(q, a) \to (q\_A, b, m)$ of $T$ (where $q$ is a state of $T$, $a,b \in \Gamma$, and $m \in \\{\text{left}, \text{right}, \text{stay}\\}$ is the movement of the head) with the four transitions $(q, a) \to (q\_i, b, m)$ for $i \in \\{1,2,3,4\\}$.
* Adding the transitions $(q\_i, a) \to (q\_A, a, \text{stay})$ for $i \in \\{ 1, 2, 3, 4\\}$ and $a \in \Gamma$.

$T'$ is still a non-deterministic polynomial-time Turing machine that decides $L$. Moreover, if $x \in L$ then $T'$ with input $x$ has at least $4$ accepting paths, therefore $L \in \mathsf{NP4}$, which concludes the proof.
> 0 votes

---
Tags: np
---


# Question
Title: Cannot understand reductions from the halting problem and its complement
When I was going through the reductions from $HP$ and $\overline{HP}$ in this handout, I do not understand how everywhere the following claim is made: $$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt on x} ⇒ M′ \text{ does not accept any strings} ⇒ L(M′)\text{ is finite} ⇒ M′ \in L\_5.$$ Why does $M$ not halting on $x$ imply that $M'$ does not accept any string at all?

My understanding initially was that $M'$ is a non-deterministic Turing machine that simultaneously runs $M$ on all possible inputs, but that doesn't seem right. Can someone please take a few examples, $(L\_3, L\_4, L\_5$ if possible) and explain how the reductions are performed?

Also, I do not understand what $\tau(⟨M,x⟩) = ⟨M'⟩$ means.

I do understand how reductions are done after reading a few pages from Sipser. I still don't understand how they're done in the linked handout though. If anyone can even comment on what book uses the same notation or the reduction procedure as the handout, it would be of a lot help!

# Answer
> 0 votes
The machine $M'$ ignores its input, and just simulates $M$ running on $x$. Hence:

* If $M$ halts on $x$ then $M'$ halts on all inputs.
* If $M$ doesn't halt on $x$ then $M'$ doesn't halt on any input.

The notation $\tau(\langle M,x \rangle) = M'$ is the definition of a reduction $\tau$ from $\overline{HP}$ to $L\_5$. The input to the reduction is an instance of the halting problem, which is a pair consisting of a Turing machine $M$ and an output $x$, and the output is the Turing machine $M'$ described above.

---
Tags: turing-machines, undecidability
---


title: A reduction of $HALT_{TM}$ to $A_{TM}$

text:
# Question
Title: A reduction of $HALT_{TM}$ to $A_{TM}$
A widely used example of reductions, is a reduction of $A\_{TM}$ to $HALT\_{TM}$.

How to show the opposite reduction, meaning of $HALT\_{TM}$ to $A\_{TM}$, if possible.

# Answer
> 1 votes
A many-one reduction from $HALT\_{TM}$ to $A\_{TM}$ means that all instances of the $HALT\_{TM}$ problem are transformed to an instance of $A\_{TM}$ (can be just one instance), such that if $A\_{TM}$ is turing-recognizable then $HALT\_{TM}$ is also turing-recognizable.

This reduction can be done by encoding a $TM$ $N$, such that $N$ accepts input string $\langle M,w\rangle$ iff $M$ halts with input string $w$. So if $M$ halts with input $w$, it means that $\langle M,w\rangle \in HALT$, which implies that $N$ accepts $\langle M,w\rangle$, and that the instance $\langle N,\langle M,w\rangle\rangle\in A\_{TM}$.

# Answer
> 1 votes
There is a reduction proof here, with a lot of context: https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/22/Small22.pdf

In short, the reduction is:

Let the machine $M'$ be defined as follows:

$M'$ = On input $⟨N, z⟩$:

1. Run $N$ on $z$.
2. If $N$ halts on $z$, accept

We run on $⟨M', ⟨M, w⟩⟩$, and get that $⟨M, w⟩ \in HALT\_{TM} \iff ⟨M', ⟨M, w⟩⟩ \in A\_{TM}$

---
Tags: reductions, halting-problem
---


# Question
Title: How to describe Deterministic Transitive Closure in FOL?
In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE.

Hence, taking into account that FOL captures LOGSPACE, the following should be possible:

* Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
* Define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)").

I would like to know how to define such predicate. This would be quite easy in Datalog, using recursion, but it should be possible to define it without recursion, which is the question that puzzles me.

# Answer
> Hence, taking into account that FOL captures LOGSPACE, it should be possible to:
>
> * Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
> * It should be possible to define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)")

Actually this is not correct: first-order logic does not capture logspace. As you said earlier in your question, FOL *plus deterministic transitive closure* captures logspace, that is $$ \text{FO(DTC)} = \text{L} $$ but $$ \text{FO} \ne \text{FO(DTC)}, $$

i.e. deterministic transitive closure is not definable in first-order logic.

More generally, FOL is quite limited. FOL captures a class called uniform $\text{AC0}$ (see the complexity zoo and Immerman's diagram); it is the class of queries computable in "constant parallel time". And transitive closure, even deterministic transitive closure, cannot be done in $\text{AC0}$ (with a circuit of constant depth). Even something very simple, calculating the parity of the number of input bits, can't be done in $\text{AC0}$.

> How to describe Deterministic Transitive Closure in FOL?

To reiterate: it is impossible.
> 3 votes

---
Tags: first-order-logic, descriptive-complexity, finite-model-theory, datalog
---


# Question
Title: Prove following statement about Kruskal Algorithm
Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this edge isn't in any Minimimum Spanning Tree of G.

# Answer
Without additional assumptions about the edge weights that's false. A simple counterexample is a triangle graph where all edge weights are equal.
> 0 votes

---
Tags: graphs, greedy-algorithms, minimum-spanning-tree, spanning-trees
---


# Question
Title: Why is DFS not suited for shortest path problem?
I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know **Can DFS we used to find the shortest path for weighted graphs?** I know that Dijkstra's algorithm is used to find the shortest path for weighted graphs. **But, what I want to know is what is fundamentally different in using DFS for unweighted graphs compared to Dijkstra (which is BFS + priority queue/set) and why can't we create DFS + priority queue/set implementation for shortest path problem?**

Ref link: Shortest Path using DFS on weighted graphs, Why can't DFS be used to find shortest paths in unweighted graphs?

Any help would be really appreciated. Thanks!

# Answer
# TL;DR Depth First Search

I believe that *Depth First search* traverses the graph by recursively visiting the unseen vertices of the current vertex until they're exhausted.

```
for all vertices fresh = true
DFS(v):
   v.fresh = false
   for all the neighbors e of v:
      if e.fresh:
         DFS(e)

```

Now, weight on the other hand, is *a restriction imposed on edges*. Hence, the usage of *Breadth First Search* becomes handy. Because we traverse the graph based on *layers* or *levels*, where we're checking all the edges at a certain vertex.

# Dijkstra's algorithm

Dijkstra's algorithm is pretty much tricky. You seen, the original paper does specify how *prioritize to vertices based on the sum of the weight for each reached vertex*.

But more importantly, it does **not** specify how to fulfill such a task. Indeed, the whole time complexity is dependent on the complexity of how we're prioritizing the vertices.

## Prioritizing the vertices

Consider an abstract data type `PriorityQueue`, where it supports the following operations for an instance `queue`:

* `void add(item)` to add an item to the instance `queue`
* `item get()` to return and remove the current top priority from the instance `queue`.

Many data structures provide these elementary operations. But the bottleneck of the algorithm is **to update the vertex's priority** in case it was reached from a less weighted edge.

Consider an operation `update(item,value)` that reset the priority of the `item` to a certain `value`. There are many ways to extend `PriorityQueue` but all of them have different complexities.

### Using Arrays

Arrays are finite contiguous chunks of memory, so we have

* $O(1)$ to `add()` any item at the end, $O(n)$, otherwise since it involves swapping.
* $O(n)$ to `get()` the current priority because we traverse the whole array.
* $O(n)$ to `update()` any item for the same reason.

### Using Heaps

Heaps are arrays that have a binary tree property, called the *heap invariant* which states the following

> *Every node is less than it's children (in the case of a MinHeap)*

This provides $O(\log\_2 n)$ to both `add()` and `get()` an item. But it costs $O(n)$ to `update()` any item's priority (since there is no order imposed on the children).

### Using Binary Search Trees (Balanced)

It has the same costs as the heap does for both to `add()` and `get()` an item. But instead of $O(n)$ to `update()`, we have $O(\log\_2 n)$. Since searching throughout the whole tree is logarethmic due to the following properties

> *Every node is greater than its left*
>
> *Every node is less than or equals its right*

### Using Fibonacci heaps

Fibonacci heaps are an advanced data structure that is a forest of MinHeap trees.
> 0 votes

---
Tags: shortest-path, weighted-graphs, dijkstras-algorithm, depth-first-search
---


# Question
Title: How to apply Arden's theory to determine a regular expression
If $P=ab$ and $Q=a^\*$, how do I use Arden's theorem to determine the regular expression $R$. I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. Also how would I use that to check that $R$ satisfies Arden's equation.

# Answer
> 1 votes
Arden's theorem states that $A^\*\\,B$ is the least fixed point of the equation:

$$ X = A\\,X\\,\cup B$$

and that $A\\,B^\*$ is the least fixed point of the equation:

$$X = X\\,B\\,\cup A$$

In your case, $R = Q\\,P^\* = a^\* (a b)^\*$.

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Maximum number of multiples of an array element preceding it
Given an array of size $n$, we have to find the maximum number of multiples of $A\[i\]$ in the array, where the indexes of the multiples should be less than $i$.

For example, given the array

> 36 40 16 24 27 12 9 4

We see that element 4 has the highest number of multiples (5) as per the given conditions, so the answer is 5.

My approach: I used brute force to solve this. I used nested loops to solve this. The first loop from the last element and the second loop from the first element to the second to last element.

Can you help me improve the running time?

# Answer
> 1 votes
**Hint**: note that if there are duplicates, we are basically only interested in the last occurrence of each value. Now if you maintain an array $C$ of size $\max\_i A\[i\]$ such that at the $i$-th iteration of your algorithm $C\_k=|\\{j\le i, A\_j=k\\}|$, how can you compute the number of multiples of $A\[i\]$ to the left of $i$ so that the overall complexity is not too high?

# Answer
> 0 votes
Maintain an array `Composite_in_Array[n]` and `Multiples[n]` initialize with zero.

```
for i=n-1 to i>=0
  if( Composite_in_Array[i] !=0 )
    for j=i-1 to j>=0
       if( A[j] % A[j] == 0 )
          Composite_in_Array[j]=1;
          Multiples[i]++;

Find the index with largest value in Multiples[]. Corresponding value in A[] will be your answer.

```

**This approach eliminates the cost of finding multiples of numbers which are already divisible by a number on their right.**

After the first few iterations, the arrays would look like this. So on the next iteration

```
A                    36 40 16 24 27 12 9 4
Multiples            0   0  0  0  0  0 0 5
Composite_in_Array   1   1  1  1  0  1 0 0

A                    36 40 16 24 27 12 9 4
Multiples            0   0  0  0  0  0 3 5
Composite_in_Array   1   1  1  1  1  1 0 0

```

The loop will not look for any more divisors since they can't be a candidate for having highest multiple counts as all their multiples are also divisible by their divisor.

# Answer
> 0 votes
Take roughly Devesh's answer with one addition:

For each integer from Array\[0\] to Array\[N-1\], we find the prime factors, and for each prime factor we create a linked list of all numbers with that prime factor, and the count of items in the list. (I'm assuming that N is so large that it can be done in O (N^2)).

Then run Devesh's algorithm. To speed up, we look at the prime factors of A\[i\], remove A\[i\] from all the lists of numbers with prime factors, then pick the list with the fewest elements, and examine those numbers only. For example, if A\[i\] = 2 * 3^2 * 113, then quite likely there are only few numbers with a prime factor 113, so we can check them quickly.

If the numbers are large so that factoring them completely is slow compared to N, then we don't need to do a complete factoring. For example, if we count numbers with one of the smallest 64 primes as a factor, and then count numbers having a larger factor, the algorithm still works. The factoring is more efficient although the counting is less efficient.

# Answer
> 0 votes
O(nlogn) approach

* First maintain a count array cnt\[\] such that cnt\[i\] stores frequency of i in your array, as well as a set to keep distinct numbers of your array
* Then go through each number in the set, go through its multiples and add up the cnt\[\]

Code (Python)

```
array = [36, 40, 16, 24, 27, 12, 9, 4]
frequency = [0] * 1000001
distinct = set()
for element in array:
    frequency[element] += 1
    distinct.add(element)
ans = 0
for element in distinct:
    current = 0
    for multiple in range(element, 1000001, element):
        # equivalent to
        # for (int multiple = element; multiple <= 1000000; multiple += element)
        current += frequency[multiple]
    ans = max(ans, current)
print (ans)

```

Complexity is O(MAXN\*logn) worse case because the elements are distinct and the complexity is O(1000000/1+1000000/2+...+1000000/m) and m can be n so O(MAXN\*logn)=O(1e6\*20) by harmonic series

Note: If you don't want to use a set, maintain another `seen` array as well as a `distinct` array. Then before you insert simply check if `seen[element]` is true.

EDIT: OOPS I MISREAD THE PROBLEM I AM SORRY

Since you only want to count multiples **preceding** it, you can modify the code such that you store the position of the occurrences, not just the frequency. (i.e. frequency\[i\] stores \[position where i occurred\]). You would also need to store the *latest* position a number appears in the `distinct` set, not just te number itself.

Then instead of `current += frequency[multiple]`, you should first binary search for the largest index that's \<= multiple, then add the number of terms.

The complexity analysis will be left as an exercise :)

---
Tags: algorithms, arrays
---


# Question
Title: Is it possible for the runtime and input size in an algorithm to be inversely related?
I'm wondering if it's possible for algorithms that have monotonically **decreasing** runtime with the input-size - just as a fun mental exercise. If not, is it possible to disprove this claim? I haven't been able to come up with an example or counterexample so far, and this sounds like an interesting problem.

P.S. Something like $O(\frac{1}{n})$, I guess (if it exists)

# Answer
Well an algorithm with $O(0)$ fulfills the criterion. It basically does nothing. As soon as your algorithm does at least one operation on execution it has a runtime cost $t(n) \> 0$. Since $$t(n)\in O(1/n) \Leftrightarrow \exists c,n\_0\forall n \>n\_0: t(n) \leq c\cdot\frac 1 n$$ An algorithm with constant runtime doesn't have runtime $O(1/n)$. This means that for a runtime measure where every operation costs at least $1$ only the empty algo has runtime $O(1/n)$ but if you e.g. say that an if-stmt with the check of an condition has cost zero you can build algorithms whos runtime cost is 0 after a certain input is reached e.g.:

```
def algo(n):
  if n < 100:
    do something very expensive

```

This algo is if you declare condition checking as 0 cost operation an algorithm with runtime $O(0)$ and thus also runtime $O(1/n)$ even though it could do a very expensive operation for the first hundred values.

Generally a decreasing complexity is rather senseless because you can always express it as either $O(1)$ or $O(0)$. (e.g. $O(1/n+10) = O(1)$).
> 8 votes

# Answer
Try brute force searching of a key for a cryptographic algorithm. The more of the key you give it to start with, the less you have to search for. True that trend stops at the limit of keysize (but that's still monotonic), and there are probably other examples in the field of extensive search where the more input data, the easier it is to prune branches of the potential tree.
> 10 votes

# Answer
Just to mention something in addition to the other (correct) answers: Such complexities can arise when the runtime of the algorithm depend on more than just one parameter / if one does not care about the input size. For example, searching the minimum in $n$ elements is clearly in $O(n)$, however, if you do this in parallel using $p$ processors, the complexity is in $O(\frac{n}{p} + \log{p})$.

Other instances this phenomen can arise are when you have a precision parameter $\epsilon$ present, which you usually want to have as close to 0 as possible. In such cases, $O(\epsilon^{-1})$ is actually "worse" than $O(\epsilon)$ because you want the error to be as small as possible.
> 1 votes

# Answer
Just reading in the (full) input is $O(n)$ for input of size $n$.
> 0 votes

---
Tags: algorithms, complexity-theory, time-complexity
---


# Question
Title: Are NP problems lower bounded by exponential order of growth?
My understanding of P. vs NP is quite limited. I can understand P refers to an algorithm with an upper bound (big O) with order of growth $n^c$ for some constant c and variable n. My question is, do NP problems have a hypothesized lower bound order of growth (big Omega) of $c^n$ for deterministic machines? I can't find this stated anywhere and I'm trying to understand if this is something that is assumed or not.

Thanks.

# Answer
> 16 votes
First of all, every problem in P is in NP, and so we need to change your question to involve NP-complete problems rather than just NP problems.

The Exponential Time Hypothesis states that 3SAT requires exponential time $c^m$ for some constant $c \> 1$, where $m$ is the number of variables. The Strong Exponential Time Hypothesis states that $k$SAT requires exponential time $c\_k^m$, where $c\_k \to 2$.

However, your conjecture is unconditionally false. Consider the language $L$ consisting of all pairs $\langle x,y \rangle$ such that $x$ is a 3SAT instance on $m$ variables (in particular, $m \leq |x|$), and $y = 0^{|x|^{100}}$. The language $L$ is clearly NP-complete, but it can be solved in time $2^m \mathit{poly}(n) = 2^{n^{1/100}} \mathit{poly}(n)$, where $n$ is the input size.

The Exponential Time Hypothesis does imply that every NP-complete problem requires time $c^{n^\alpha}$, for some $c\>1$ and $\alpha\>0$. This kind of running time is sometimes called subexponential time, but unfortunately this expression has several different interpretations, depending on context.

---
Tags: complexity-theory
---


# Question
Title: Complexity of "does a directed graph have <=1 Hamiltonian cycles?"
I am studying the complexity classes and I am confused what is the complexity of the following problem: *"Does a directed graph G has at most 1 Hamiltonian cycle?"*

So, from my knowledge and understanding:

1. Existence of Hamiltonian cycle is a NP(C) problem.
2. Existence of exactly $k$ ($k\>1$) Hamiltonian cycles in a graph belongs to PSPACE.
3. The stated problem would be a complement of *"Does a directed graph G has at least 2 Hamiltonian cycles?"*

However, I still fail to see to which class the mentioned problem belongs. Originally I though it would also belong to PSPACE, but not to any space in PSPACE. However, I have consulted my teacher and she said that, while it belongs to PSPACE, it also belongs to some subset of PSPACE. Which subset that would be? Does it belong to co-NP, and the problem from 3. then belongs to NP? If yes, how to prove it (because for now I'm just guessing it based on my teachers' hint)? If no, where does it belong?

# Answer
> 1 votes
Your problem clearly belongs to $\mathsf{co\text{-}NP}$. An easy "no" certificate consists of 2 distinct Hamiltonian cycles. The certificate can clearly be checked in polynomial-time.

The same certificate is also a "yes" certificate for problem in 3 (i.e., "Does a directed graph G has at least 2 Hamiltonian cycles?"), showing that it belongs to $\mathsf{NP}$.

---
Tags: complexity-theory
---


# Question
Title: How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?
I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular.

If the alphabet is $\Sigma = \\{a, b\\}$ and the language is $L = \\{a^{i + 1} b^{4i + 2} \mid i \in \mathbb N\\}$, how do I prove the language is not regular using pumping Lemma?

Also what is a pumping length, how do i know to assign a pumping length to the language stated above?

# Answer
Since I see questions about the pumping lemma on this site quite often, I decided to write a bit of a longer answer hoping that it helps people "get" the PL rather than just treating it as a "plug-n-chug" tool given to us by the gods of math.

## Understanding the PL

I think the best way to go about it is to basically (re-)derive the lemma. The idea is that if some language $L$ is regular, then there exists some DFA $A$ such that $A$ recognizes $L$. Now say that $A$ has $m$ states and suppose that we have some $w \in L$ with of length $n \> m$ (note that any infinite $L$ must contain such a word) and consider the run of $A$ on $w$.

As $w$ has more characters than $A$ has states, there must be some state $q$ which occurs at least twice in $A$'s run on $w$, i.e. if we draw out the run through the graphic representation of $A$ we find some loop. In more formal terms, this means that there must be some substring $s$ of $w$ -- so $w$ can be written as $w = rst$ where $r$ and $t$ are remaining parts of $w$ left and right of $s$ -- such that $A$ is in state $q$ on the both the first and last symbol of $s$.

At this point, we need to understand the D part of DFA: $A$ is deterministic, so given that we start from the initial state on any input of the form $r\Sigma^\ast$ (any string starting with the substring $r$) we will always end up at the state $q$ and similarly, starting from $q$ on the word $s$ we always end up at $q$ again and finally, starting on $q$ given the word $t$ we always end up at the same (accepting) state. I like to think of such deterministic machines as music boxes; if you start the at the same point they end up playing the same melody.

This means that we can now create new words which $A$ must also accept by making $A$ go into state $q$ and presenting it with $t$, and the easiest way to do so is by taking the known string $r$ to get it to the state $q$ initially, then repeating $s$ some $k \geq 0$ times (which, because we start at $q$ now) will always get us back to $q$ and then appending $t$ to make $A$ go into an accepting state. Hence these words are of the form $w\_k = rs^kt$ for some $k \geq 0$.

Taking a step back, we have now basically argued that $A$ cannot distinguish between $w$ and $w\_k$; the result of the computation will always be the same. This is the essence of how the pumping lemma works.

## Using the PL

To apply the pumping lemma we must now find such $w$ and $k$ where $w \in L$ and $w\_k \notin L$. Usually one will not be able to give $w$ directly as the size of the automaton $A$ is unknown (in fact we are trying to argue that such an $A$ does not exist, so yeah). In most cases, this boils down to taking a "large" string in $L$ such that the middle part of said string is big enough for us to find some part that if repeated would give us the $w\_k$ we need.

Let us get specific now. Our language is $L = \\{a^{i + 1} b^{4i + 2} \mid i \in \mathbb N\\}$. We assume that $L$ is regular and thus admits a DFA $A$ of size $m$. If we consider the string $w = a^{10m + 1} b^{40m + 2} \in L$, we find that a state repetition must already occur in the $a$-part of $w$ as $a^{10m + 1}$ has more symbols than $A$ has states. Hence there must be a decomposition $w = rst$ where $r = a^{\ell}$, $s = a^k$ and $t = a^{10m + 1 - \ell - k} b^{40m + 2}$ with $0 \leq \ell \< m$ and $0 \< k \leq m$ (Can you figure out why the bounds on these variables are this way? This is a good test to see if you are confident with the first part, I think).

If we now consider the word $$ w\_2 = rs^2t = a^\ell (a^k)^2 a^{10m + 1 - \ell - k} b^{40m + 2} $$ and unpack it to $$ a^{m + k + 1} b^{40m + 2} $$ we see that $w\_2$ is not in $L$. It follows that $A$ does not recognize $L$ as we assumed that $A$ accepts $w \in L$ and then argued that it must also accept $w\_2 \notin L$. As the choice of $A$ was arbitrary we find that no DFA can recognize $L$, which means that $L$ is not regular.
> 3 votes

# Answer
Assume the language is regular, i.e., there is an automaton that recognize the language with a finite set of states. Therefore there are $i \neq j$ such that processing $a^{i +1}$ and $a^{j + 1}$ reach the same state X. Processing $4i + 2$ b's in state X always ends up in the same state Y. State Y must be accepting because $a^{i + 1} b^{4i + 2}$ is in the language. At the same time it must not be an accepting state, because $a^{j+ 1} b^{4i + 2}$ is not in the language when $i \neq j$. Contradiction, so the language is not regular.
> 0 votes

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


# Question
Title: Randomly generating graph based off number of connections on each node
I'm trying to generate a graph based off some data I have.

This graph should have `N` nodes where the number of edges each node has is equal to a random number `P(k)`, where k is the "index" of the node (mostly arbitrary).

My question is, is there an actual way to do this? I'm thinking that I need more data that either determines the density or another degree of connections out (N1-\>N2-\>N3), but I'm not entirely sure.

# Answer
> 1 votes
You essentially want to generate a graph with some degree sequence (which you want to be random, but this is not relevant); this is called the graph realization problem which is solved e.g. by the Havel-Hakimi algorithm in the sense that the algorithm will return a (simple) graph with the desired degree sequence if that is possible (such sequences are called *graphic*). Note that not all finite sequences over $\mathbb N$ are graphic as e.g. any sequence whose members sum to an odd number cannot be graphic by the handshake lemma (which states that the sum of all degrees in a graph is equal to 2 times the number of edges in a graph and thus even). Further, the solutions will in general not be unique: The degree sequence $(2, 2, 2, 2, 2, 2)$ for example can be realized by the cycle graph $C\_6$ of size $6$ or the disjoint union $C\_3 \mathop{\dot\cup} C\_3$ of two cycle graphs $C\_3$ of size $3$ each.

Many graph libraries for programming languages have implementations of algorithms for this problem, for example the Python library networkx.

---
Tags: graphs, randomized-algorithms
---


# Question
Title: What is a dominator node and a dominator tree?
I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node:

> a node d dominates a node n if every path from the entry node to n must go through d.

I need to understand the concept of a dominator node but I do not need to go deep into graphs, so I'm trying to make sense of these definitions. I'm trying to look in the images on the article:

This is a graph:

This should be a dominator tree for the graph above:

Based on the definition above, I think

node 2 dominates node 3 because every path from 3 must go through 2. Why? To go from 3 to itself I must pass to 2. That's why 2 goes to 3 in the dominator tree.

Am I thinking right?

Can I know also why this is useful in compilers?

# Answer
> 3 votes
The reason you give is not exactly right; the definition of a dominator node works from a starting node ($1$ in the example). The only way to reach $3$ from $1$ is to go through $2$ as it is the sole successor node of $1$ in the given graph. Hence $2$ dominates $3$. For the same reason, the nodes $4$ through $6$ are also dominated by $2$ and further, $2$ is the *immediate* dominator of these nodes (as $1$ dominates $2$) and these nodes are also not dominated by any other nodes than $1$ and $2$:

* $3, 4$ and $6$ can be immediately reached from $1$ via $2$.
* $5$ can be reached from $2$ either via $3$ or $4$ and thus the only common nodes in these paths to $5$ are $1$ and $2$.

As for applying these concepts to compilers, consider a block-level control flow graph (or CFG for brevity) of a program. If some block $B$ dominates a block $B'$ in the CFG, then $B$ must have been executed by the time the program reaches $B'$. This knowledge can be used to remove redundant pieces of code: Consider the program

```
a = (something)
b = True

if a == True:
   b = True
else:
   b = False

```

Here, the block consisting of the first two lines dominates the if-block as well as the else-block. Hence we know that by the time we jump to the if-block where we would set b to True, it is already set to True by the fist block and thus the compiler could optimize the code by deleting the assignment in the if-block.

You can also detect loops in the code by analyzing if the CFG has edges of the form $B' \to B$ where again $B$ dominates $B'$. Such a path indicates the existence of a loop where $B$ would then represent the loop header while $B'$ is (the last) part of the loop body.

---
Tags: graphs, trees, compilers
---


# Question
Title: Is a graph at least k-colorable? (Complexity)
I am new to the complexity theory and I am trying to understand what would be the complexity of the following problem: *"Is a graph AT LEAST $k$-colorable?"*

Whether a graph is $k$-colorable is clearly a NPC problem and is explained by reduction to 3-SAT.

However, I am not sure to which complexity class belongs the modified problem I have stated. Does it belong to NP as well? My guess is that we would be able to check it with a polynomial certificate (any $\geq k$ coloring of the graph).

And then the problem *"Is a graph AT MOST $k$-colorable?"* would be its complement in co-NP unless NP=co-NP?

# Answer
Well, all graphs are colorable with $\geq k$ colors: Assign each vertex a different color (and leave the other color classes empty if $k$ is larger than the number of vertices of the given graph).

As for the complement of this problem, note that you did not correctly invert the definition of the problem: A problem $L$ is, after all, merely a set of strings over some finite alphabet $\Sigma$ representing some objects with some property. Its complement is then the set $\Sigma^\ast \setminus L$ or the set of all strings *not* representing an object with the property. If we recall the argument above, we find that the complement of your problem is hence the set of all strings not representing graphs (under that fixed encoding scheme) rather than the one you claimed. This problem (as the first one), is in $\mathsf P$.
> 0 votes

---
Tags: complexity-theory
---