# Question
Title: Standard Parameters for Genetic Algorithms
I'm currently writing my thesis, which uses genetic algorithms at some point. Now I need to define some parameters for the genetic algorithm

I know that, because of the No Free Lunch Theorem there is no optimal parameter configuration for all problems.

However I do need some default parameters, because finding the optimal parameters is out of scope of my paper. Also I don't want to use random values as these parameters.

I would prefer to reuse parameters used in some well trusted sources in the field of genetic algorithms. Then I could rely on these cited sources and reuse these parameters.

I need default values for these parameters:

* population size
* mutation rate
* number of generations

I searched for papers, but am not sure which paper is well-known. I'm looking for papers that are well-known and have these parameters used. A online available pdf is preferable.

# Answer
> 4 votes
As you say, there are no universal parameter settings, which means that you won't find a source that cites any such settings. Instead, you find some papers who tune the parameters to their particular problem, and you find many, many others that simply take a "standard" set of parameter settings without much attempt to justify them. In that case, it's not like there's a single authoritative source you can cite -- it's more like bunches of people sort of converge on parameters that seem common to everyone. The best you can really do is to say something like "the parameter values were chosen as being commonly observed in the literature."

Also, it depends not just on the problem, but on the particular structure of your GA. CHC (Eshelman, 1991), for example, is usually used with a population size of 50 (very small by typical standards) and has no conventional mutation operator, but it adds other pieces that make up for it. Genetic programming practitioners often use population sizes in the thousands and use very high mutation rates.

For a "standard GA", if you were to use a population size of 100-200, a mutation rate of 1/L (with L=the length of your encoding, assuming it's discrete), and "enough" generations (more on that in a second), no one would question things too much. However, aside from just citing a random selection of papers, there's not a lot you can point to as justification. Also, some light parameter tuning is almost certainly a better idea if you can afford it at all.

For generation count, the basic rule is to go until you either exhaust the amount of time you have to allot to it or until the algorithm converges, whichever comes first. Of course, these are interdependent. Raising the population size and/or raising the mutation rate will slow convergence, so you still need to tune parameters for the best results.

If you're doing this for research purposes at least, you should also measure the runtime in fitness function evaluations rather than generations. The reason is that if my algorithm finds a solution in N generations, you can almost certainly find a better solution in N generations if you just multiply the population size by 100 or so. You'll get to do about two orders of magnitude more searching than I could do, so the comparison is unfair. Reporting generations used is an automatic red flag in a paper unless the other GA parameters are controlled to a degree that we can be sure that the comparison is apples to apples. Measuring evaluations is much more tightly correlated to wall-clock time than measuring generations, and should essentially always be preferred.

# Answer
> 1 votes
For population size you should see my other answer.

For mutation I found a reference in this paper (page 13):

> The rule of thumb is that if the selection pressure used is that associated for instance with the Microbial GA using tournaments of size the optimal mutation rate is in the region of one mutation per genotype after taking account of any junk or neutral mutations

Finally, the default value for the number of generations is, as deong pointed out, whatever available time you have that will result in a reasonable solution to your problem or until your genotypes converge to an optimum (however this is tricky as they could be converging to one of several local optima).

# Answer
> 0 votes
as indicated by the other answer there are no standard parameters unless you are working with models that have been created by others or attempting to mimic them. however heres another angle on this. you ask specifically about 3 key GA parameters. there are standard *indicators* obtained from GA evolution of whether your parameters need to be adjusted.

* population size — if your population is too small, the improvement per iteration in the fitness function will be low (measured as the best candidate solutions or the average of solutions). if you increase the population size and the fitness function increases faster then its a sign its suboptimal. also there is a point where increasing the population size does not improve the rate of increase in the fitness function.
* mutation rate — if its too low the algorithm will not cover the search space much. if its too high then good candidate solutions will be perturbed and pushed into worse solutions. again basically a rough measure is the rate of improvement in the fitness function.
* number of generations - the number of generations is related to improvement in the fitness function. a fitness function usually shows major improvement in early generations and then asymptotically approaches an optimum. after enough trend you can determine what the theoretical optimum is from fitting/extrapolating this line, and how much improvement per time is possible.

# Answer
> 0 votes
This question reminds me of a whole area called "meta-optimization". Where the objective is to find suitable parameter settings for a particular evolutionary search algorithm (for a specific problem), and the search is done by another "upper-level evolutionary" process. If your problem does not involve costly function evaluations, then such type of "meta-optimization" could be easily implementable. So far I remember, ECJ already offers such type of implementations.

The settings are inherently dependent on the nature of the problem that you are trying to solve. However, population size could be "somewhat" estimated, see this paper for more details.

---
Tags: genetic-algorithms
---


# Question
Title: Evolutionary algorithm - how to select the parents
I try to solve Physical Travelling Salesman Problem using evolutionary algorithm and I have diffucult to detemine how to choose the parent , on which we do the crossover.

Assume I have popultion of 100. The parent should be selected randomally? or according to their fitness? If I choose them randomally I don't think the result be enough good but in the other hand, if I will choose the 2 with the best fitness, I will always choose the same! (Maybe child of them , but most of my population will never be choosed!).

What I miss?

I also need some advise on how to calculate fitness. The parameters are the amount of waypoints each van collect and the total time.

My problem here is becuase there are unit that don't manage to collect any points and thus thier fitness is 0 and step by step my array full with 0....(I am working with the code here : http://www.ptsp-game.net/ ant there is problem of time exceed..)

# Answer
> 5 votes
As a simple method, you can use the roulette wheel selection. The idea is that *every* individual has a chance to be selected as a parent, but the more fit an individual is, the more likely it is to be selected. Let $f\_i$ be the fitness of the individual $i$. The probability $p\_i$ of choosing $i$ as a parent for the next round is $p\_i = f\_i / \sum\_{j=1}^{N}$, where N is the size of your population.

Here's an example in the context of TSP. For simplicity, let's say your population is only 4 individuals. Assume every individual is a tour of some length. The shorter the tour, the higher the fitness. Let the fitness values of the tours be $F = \\{ 25,15,10,5 \\}$. The sum of elements is 55. We divide every element $f\_i$ with 55, and obtain $\\{ 0.45, 0.27, 0.18, 0.09\\}$. To implement the roulette wheel, you can use a weighted random generator if the language provides one (if not, just roll your own).

If you want to experiment with other *genetic selection operators*, look up other more complicated selection methods. To get you started on those, have a look at selection operators.

# Answer
> 0 votes
There is also the tournament selection which can be used in conjunction with the simple microbial genetic algorithm as outlined in this paper.

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


# Question
Title: Determining the minimum number of edges to add in order to be 3-connected
A graph $G$ is said to be $3$-connected if it has no $2$-vertex cutsets (i.e., at least three vertices must be deleted to disconnect the graph). As far as I know, it is possible to determine if a simple graph is $3$-connected in $O(n)$ time (example: http://www2.tu-ilmenau.de/combinatorial-optimization/Schmidt2012b.pdf), but I would find it useful to efficiently determine which edges to add in order to make our graph $3$-connected if it isn't already (ideally, the minimum number of edges if this can be done efficiently). Is anyone aware of such an algorithm? If so, I would appreciate a reference or two.

# Answer
> 5 votes
For this special case of $3$-connectivity, it has been solved by Watanabe and Nakamura. The algorithm runs in $O(n(n+m)^2)$ time, where $n$ and $m$ are the number of vertices and edges of the input graph, respectively.

There is a polynomial time algorithm to find the minimum number of edges to add to a $k-1$-connected graph to produce a $k$-connected graph. See chapter 3 of László A. Végh's PhD thesis. The thesis states that it is not known if adding a minimum number of edges to produce a $k$-connected graph is NP-hard in general.

---
Tags: algorithms, graphs, reference-request
---


# Question
Title: Concise way to say "increases with n or some term of n"
I'm writing a thesis proposal and one of the systems involved has unknown complexity. It's not a focus of the proposal, but I wanted to include a line like this, as speculation:

> Presumably the complexity of each new connection scales with the number of rules.

Unfortunately I don't know if asymptotic complexity (space and time) will be O($\log{n}$), O($n$), O($n\log{n}$) or even O($n^{99}$). But I do doubt that it will be constant, so increasing $n$ will have some effect on it.

What is a good, **accurate** way to write this concisely? I'm asking here and not at English Language and Usage because the CS accuracy is essential.

# Answer
> 1 votes
"Presumably the complexity of each new connection is **an increasing function of** the number of rules."

But you don't mean complexity. Problems have complexity, algorithms have running time (or, more generally, resource usage), functions have growth rate.

---
Tags: complexity-theory, terminology
---


# Question
Title: Break and Continue in Structured Programming?
One of the ways to ensure following the structured programming paradigm is by having all control flows having only one entry and one exit point. Does skipping iterations by using break and continue in languages like Java count as a second exit point (like a GOTO-statement) or not?

I am aware that Java has no (working) goto statement but a break and continue. The question was whether using them violates the structured programming paradigm or not, i.e. is it bad code style or not (in all languages having break and continue, not just Java).

# Answer
That of course depends on how exactly we define structured programming. We can look to the research papers that coined the phrase, such as the 1966 Structured Programming Theorem. Structured programming, as defined in these papers, would not permit partial execution of a loop body, and therefore neither a `break`, `continue`, `return` or `throw` statement (nor any exceptions thrown by the JVM).

All of these language features were invented *after* structured programming, and to address perceived deficiencies of structured programming (in its original definition). Whether these amendments comply with the spirit of structured programming (or equivalently, whether a modern definition of structured programming should encompass these features) has been the topic of some debate, see for instance the 1995 paper Loop Exits and Structured Programming: Reopening the Debate.

Personally, I find applying this 1966 programming technique, ground breaking as it was at the time, verbatim to a modern programming language such as Java an undertaking of very questionable benefit, not the least because structured programming (in its original definition) does not permit exceptions, but exceptions are an integral part of the Java language.
> 6 votes

# Answer
There are probably many accounts of what structured programming is or should be, besides the good historical references and account provided in meriton's answer. But none of this should be perceived as mathematical definitions that should be strictly obeyed by programmers. Some of it may have been tightly formalized for the purpose of proofs that a given style has some good (or bad) properties, such as the Boehm-Jacopini theorem. But that does not imply that such formalization had to be strictly followed in practice, or even had that much impact on the programming community.

Now, the spirit of the structured programming, in the sixties and (early?) seventies was mainly to introduce some kind of organization and readability in a very messy programming world. It never was a tight set of rules to be strictly obeyed, even when some authors did give their own sets of rules to suggest a proper style.

At the time, few people understood how to organize programs around data structures. Programming was more centered around control flow, as programming was perceived as giving orders to a computer. It was common practice to first draw a flowchart, with arrows in all directions, and then translate it into (spaghetti) code, with labels and `goto` statements to implement the arrows of the flowchart. Structured programming was a reaction to this disorganized practice, and an important concept became the block of statements, or the compound statement. Basically, a program was obtained by composition of such well defined structures, that were to be entered and exited in well identified places. Exceptions as a programming concept were not yet clearly understood and were (part of) the topic of PhD dissertations). The purpose was mainly to do away with the disorder permitted by the use of the `goto` statement. Still, it was sometimes a real problem not to have, or use, the `goto`, precisely because exceptions were not yet available.

With such a view of things in mind, using `break` and `continue` in loops is a very disciplined use of loops that would have been considered quite acceptable for structureed programming.

This can be put in relation with the use of static scoping. The `goto` was bad because it created disorder in the control structure, and you never knew how control structures where entered, where control came from after passing a label, or how a statement could be exited (it could even be hidden in a subprogram, since a function could be exited with a goto, which also allowed a poor man's exception), which made programs hard to read, understand and maintain. Dynamic scoping had a similar problem with the role of identifiers, since the meaning of a free identifier in a function could depend on were the function had been called (many possible places), as opposed to static scoping where it depend only on where the function was declared (only one place). Both were intended to easily identify key points in the program structure, rather than have them duplicated and spread all over the program.

In a way, structured programming was for control what OO programming was later for data. But there is still no unique model of OO programming, and there is no reason to expect more regarding structured programming.
> 1 votes

---
Tags: java, programming-paradigms
---


title: Prove that $\neg 0 = 1$

text:
# Question
Title: Prove that $\neg 0 = 1$
Starting from this definition https://en.wikipedia.org/wiki/Boolean\_algebra\_%28structure%29#Definition, is the following a valid proof that $\neg 0 = 1$?

Instantiate a ∨ ¬a = 1 with a:=0 to get 0 ∨ ¬0 = 1 Then use pattern matching (and commutativity) against a ∨ 0 = a to get a = ¬0 on the LHS and a=1 on the RHS, thus ¬0 = 1.

To clarify the "pattern matching": We have

* 0 ∨ ¬0 = 1
* 0 ∨ 1 = 1 (from 0 ∨ a = a)
* 0 ∨ 0 = 0 (also from from 0 ∨ a = a)

If there are only the two elements 0 and 1 available, ¬0 = 1 should follow from this. But then again, if it were not true that ¬0 = 1, we would have that ¬0 = 0, which wouldn't make too much sense...

Are there other/simpler proofs?

# Answer
It's a valid proof in the sense that it convinces an appropriately skeptical reader that $\neg 0 = 1$. The argument is as follows.

1. By an axiom $0\vee \neg 0 = 1$.
2. We know that either $\neg0=0$ or $\neg0=1$.
3. We can't have $\neg0=0$ because $0\vee0=0$.
4. So it must be the case that $\neg0=1$.
5. Actually, let's check that: $0\vee 1=1$. Good.

However, that's not a proof from the axioms. Of the steps that you've used, only 1 is actually an axiom.

Step 2 is the law of excluded middle, which isn't actually one of the axioms. If you think about it, it's not actually *obvious* that every formula evaluates to exactly one of 0 and 1 (in particular, there are no formulae that evaluate to both 0 and 1, and none that evaluate to either). The law of excluded middle can be proven from the axioms but it's not an axiom.

Step 3 uses an axiom ($a\vee0=a$ instantiated with $a=0$) to deduce that $0\vee 0=0$ but there's no axiom that says you can use this to conclude that $b\neq 0$ if $a\vee b\neq a$.

Step 4 is restating the law of excluded middle.

In step 5, you could use some axioms to deduce that $0\vee 1=1$ ($0\vee 1 = 1\vee 0 = 1$) but, again, there's no axiom allowing you to draw the ultimate conclusion.

Students often get confused about axiomatic proofs: the usual complaint is "I don't know what I'm allowed to use." Confusion about that is very understandable: you've spent your whole life "knowing" that $\neg0=1$ and treating that as (half of) the definition of negation. If you're not allowed to "know" something as basic as how negation works, what on earth are you allowed to know? (Students have exactly the same problems with elementary group theory.)

For an axiomatic proof, it's actually quite simple: you're allowed to use the axioms, instantiated however you please.1 If you can prove something from the axioms, you're allowed to use that repeatedly, as a lemma: for example, I proved above that $0\vee 1=1$ so you could use that as many times as you want, after proving it once. But that's all.

Alexey Romanov included a proof in his comment to the question. I'll write it out a little more fully.

$$\begin{align\*} \neg0 &= \neg0 \vee 0 &\text{($0$ is the identity for $\vee$)}\\ &= 0 \vee \neg0 &\text{(commutativity of $\vee$)}\\ &= 1 &\text{(instantiate $a\vee\neg a=1$ with $a=0$).} \end{align\*}$$

Because of the limited resources available to you, axiomatic proofs tend to be rather fiddly and tedious, which is why we don't do them after the first week of the course. Pedagogically, I think it's actually a mistake to start with axiomatic proofs because they confuse the students more than they help. I think it would be better to introduce them later in a course, after the students are already used to proving things.

---

1. OK, and transitivity of equality and probably *modus ponens*. But I'm just putting this here for the experts to think about; for the beginner, this footnote is more likely to confuse than clarify.
> 2 votes

---
Tags: proof-techniques, boolean-algebra
---


# Question
Title: What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?
I'm having trouble understanding the definitions for complexity classes in the arithmetic heirarchy, and because of the naming schemes, "Googling" things is somewhat difficult. Can anyone provide me concrete examples of what it means for something to be $\prod\_x^y$-complete or $\sum\_x^y$-complete, and when we can say that a problem is undecidable for some $(x,y)$?

# Answer
The search term you're looking for is "arithmetical hierarchy".

# The arithmetical hierarchy

All of the following relates to the logical language of Peano arithmetic. The operations available to us are the unary successor function $S$, the constant $0$ and the binary relation $=$, all with the usual, obvious meanings. Variables range over the natural numbers.

In the notation $\Sigma\_n^m$ or $\Pi\_n^m$,

* $\Sigma$ denotes a formula equivalent to one in prenex normal form with an existential quantifier outermost;
* $\Pi$ denotes a formula equivalent to one in prenex normal form with a universal quantifier outermost;
* $n$ denotes the number of quantifier blocks;
* $m$ denotes the kinds of objects being quantified.

A formula is in $\Sigma\_0^0=\Pi\_0^0$ if it contains no quantifiers. A formula is in $\Sigma^0\_{n+1}$ if it is equivalent to one of the form $\exists x\_1, \dots, \exists x\_k\\,\varphi$, where $\varphi\in\Pi\_n^0$. A formula is in $\Pi^0\_{n+1}$ if it is equivalent to one of the form $\forall x\_1, \dots, \forall x\_k\\,\varphi$, where $\varphi\in\Sigma\_n^0$.

All of the quantifier aboves are first-order: they range over the natural numbers. Call the natural numbers "level $0$" objects and define level-$(m+1)$ objects to be sets of level-$m$ objects (or, equivalently, functions from level-$m$ objects to $\mathbb{N}$). $\Sigma\_n^m$ and $\Pi\_n^m$ extend the definition of $\Sigma\_n^0$ and $\Pi\_n^m$, respectively, by allowing quantification over objects at any level between $0$ and $m$, inclusive.

# Completeness

So far, we've only talked about formulae but a set $X\subseteq \mathbb{N}$ is said to be in $\Sigma\_n^m$ if there is a formula $\phi(x)\in \Sigma\_n^m$ with one free-variable such that $X = \\{x\mid \phi(x)\text{ is true}\\}$; similarly for $\Pi\_n^m$.

Completeness just means what it always means. A set is complete for $\Sigma\_n^m$ if it's in $\Sigma\_n^m$ and every other set in $\Sigma\_n^m$ can be reduced to it (similarly for $\Pi\_n^m$-completeness). The notion of reducibility is usually either many-one reductions or Turing reductions. So, for example, a set $Y$ is complete for $\Sigma\_n^m$ under Turing reductions if, for every set $X\in\Sigma\_n^m$, there is a Turing machine with an oracle for $Y$ that decides membership of $X$. For many-one reductions, we insist that the oracle is called only once and the result of the oracle must be the result of the Turing machine's computation. (Many-one reductions are the ones usually used to prove **NP**-completeness but, here, we're not restricting to polynomial-time reductions.)
> 5 votes

---
Tags: complexity-theory, recursion-theory
---


# Question
Title: How to reduce MAX-2SAT problem to finding a cut in a graph
I'm trying to reduce the MAX-2SAT problem to finding a cut in a graph, with no luck so far.
Let me first show a description of the problem:
**2SAT**: Given a boolean formula $\varphi$ in a CNF form, where every clause has 2 literals (a variable or its negation), one should decide whether there is an assignment that will satisfy $\varphi$.
The 2SAT problem is in $P$.

**MAX-2SAT**: Given a boolean formula $\varphi$ in a CNF form, where every clause has 2 literals, and $k\in \mathbb{N}$, one should decide if there is an assignment that will satisfy at least $k$ clauses in $\varphi$.
This is an $NPC$ problem, and I'm trying to reduce it to finding the maximum cut in a graph:
**MAX-CUT**: Given $(G=(V,E), w, k)$, where $G$ is an undirected graph, $w$ is a weight function; $w: E\rightarrow \mathbb{N}$ and $k\in\mathbb{N}$, one should decide whether there exist a cut $(V\_1,V\_2)$, s.t its weight is at least $k$, meaning $k\leq \sum \_{u\in V\_1, v\in V\_2}w(u,v)$.

I tried some obvious constructions that didn't work, like setting:
$G=(V,E)$
$V=\left \\{ v\_x|x\text{ is a literal in } \varphi \right \\}$
$E=\left \\{(v\_x,u\_z)|\text{ There exist a clause } x\vee z \text{ in } \varphi\right \\}$
and finally setting $w(e)=1$ $\forall e\in E$

This obviously didn't work, since having $k$ satisfied clauses in $\varphi$ does not imply a $k$-weighted cut in $G$.
(If the above can be improved to achieve the desired reduction, I would love to get some guidance)
I looked around online, and found that it is possible to construct an "implication graph" from $\varphi$, where every clause $(x\vee z)$ in $\varphi$ is translated to the equivalent logical expressions: $\bar{x}\Rightarrow z$ and $\bar{z}\Rightarrow x$, and these, in turn, are translated to vertices $\bar{x}, z, \bar{z}, x$, and **directed** edges $\bar{x}\rightarrow z$ and $\bar{z}\rightarrow x$, but I just can't see how that helps, since, again, $k$ satisfied clauses in $\varphi$ does not imply $k$-weighted cut in $G$.
Any help would be greatly appreciated.

# Answer
Idea: Have two vertices $x,\bar{x}$ for each variable, and connect them with an edge with some large weight which will force any maximal cut to put them in different parts of the cut. The idea is that for any two variables $x,y$, $x$ and $y$ get the same truth value iff the *vertices* $x,y$ are in the same part of the cut. This way you encode a truth assignment.

For each clause $x \lor y$, we would like to do something of the following sort: add a vertex $\varphi\_{x \lor y}$ and connect it to both $x$ and $y$. In order to guarantee that $\varphi\_{x \lor y}$ is in some specific part of the cut, add a new vertex and connect it to *all* "clause" vertices with an edge having some large weight. This idea doesn't quite work since the value of the cut depends on how many literals satisfy the clause. Find a way to fix it.
> 2 votes

# Answer
While direct reductions from MAX 2-SAT to MAX-CUT do exist (e.g. see problem 7 of this homework assignment), I think an easier reduction from MAX 2-SAT to MAX-CUT would be to first reduce MAX 2-SAT to Quadratic Unconstrained Binary Optimization (QUBO) and then reduce QUBO to MAX-CUT, because the first reduction is trivial and the second is a well-known reduction.

Clause $x\_i \vee x\_j$ is equivalent to $x\_i+x\_j-x\_ix\_j$; clause $\bar x\_i\vee x\_j$ is equivalent to $1-x\_i+x\_ix\_j$; clause $x\_i\vee \bar x\_j$ is equivalent to $1-x\_j+x\_ix\_j$, and clause $\bar x\_i\vee \bar x\_j$ is equivalent to $1-x\_ix\_j$. Therefore, we could recast the MAX 2-SAT objective of maximizing the number of satisfied clauses as the QUBO objective of maximizing a quadratic function of binary variables.

All that remains is to cast the QUBO problem as a MAX-CUT problem. There is a well-known reduction from QUBO to MAX-CUT due to Hammer (1965). Consider QUBO instance $\max \sum\_{i\neq j} q\_{ij}x\_ix\_j + \sum\_i c\_ix\_i$. Construct a graph with one node $y\_i$ for every variable $x\_i$ in the QUBO instance in addition to super-node $S$. Define the weights of each edge between $y\_i$ and $y\_j$ to be $w\_{ij} = -q\_{ij}$ and define the weight between each $y\_i$ and $S$ to be $w\_{iS} = c\_i + \sum\_j q\_{ij}$. A bit of algebra shows that you can construct the optimal QUBO solution $x^\*$ from the optimal MAX-CUT solution $y^\*$ by setting $x\_i^\*=1$ if $y\_i^\*$ lies across the cut from $S$ and $x\_i^\*=0$ if $y\_i^\*$ lies in the same set as $S$.
> 2 votes

---
Tags: reductions
---


# Question
Title: Characterizing the range of a polytime function
Is it true that an infinite language is in P iff it is the range of a length increasing polytime function? I ask because I know that it is a basic result in computability theory that a set is recursive iff it is the range of an increasing recursive function and I was wondering if there might be an analogue in complexity theory.

I know that the "length increasing" (or at least monotone increasing) is a necessary one because otherwise we could construct the Halting Problem: Just have a polytime algorithm test computation histories for a given Turing machine $M$ on input $x$ and map valid halting ones to $(M,x)$. I also know that every language in P reduces to any NP-complete language and these languages are not in P (unless of course P=NP), but I think my question might be different: I am interested in the exact image of a function over ${\Sigma}^{\*}$ and not if it happens to be properly contained in an NP-complete set. However, I don't know where to go from there. I would greatly appreciate any hints or counterexamples to demonstrate that my conjecture is false. Thanks.

# Answer
Your statement (with *length increasing* replaced with *length non-decreasing* and with functions allowed to return $\bot$, i.e. nothing) is equivalent to $\mathsf{P}=\mathsf{NP}$.

We start with two observations:

1. Every language in $\mathsf{P}$ is trivially the image of a length non-decreasing function (that's why we allow returning $\bot$).
2. If $f$ is a length non-decreasing polytime function then $y$ is in the range of $f$ iff there exists $x$ of length at most $|y|$ such that $f(x) = y$, and so the range of a length non-decreasing polytime function is always an $\mathsf{NP}$ set.

If $\mathsf{P}=\mathsf{NP}$ then the range of a length non-decreasing polytime function is always in $\mathsf{P}$, and so your (modified) statement is correct.

Suppose now that $\mathsf{P} \neq \mathsf{NP}$. Consider the language $\mathsf{SAT'}$, obtained from $\mathsf{SAT}$ by padding a formula of length $n$ with $n$ zeroes. The language $\mathsf{SAT'}$ is still $\mathsf{NP}$-complete and so not in $\mathsf{P}$. On the other hand, it is in the range of a length non-decreasing polytime function: the polytime function accepts a formula $\varphi$ and an assignment $x$, and if $x$ satisfies $\varphi$ it outputs the padded version of $\varphi$.

---

As I mentioned, you to allow the function to not decrease the length if you want $\Sigma^\*$ to be the range of some function. On the other hand, the reasoning above works as long as the function doesn't decrease the length by too much: any polynomial amount (which could depend on the function!) would work.

You can also get rid of $\bot$ if you assume that the languages you consider are not too (efficiently) sparse, that is, given a length $n$, one can find in polytime some word in the language of length at least $n$. This is the correct counterpart of the condition of being *infinite*.
> 2 votes

---
Tags: complexity-theory, reductions, polynomial-time
---


# Question
Title: Was there an attempt to make reusable regular expressions?
In everyday practice I often encounter tasks which would benefit from being able to define aliases for chunks of regular expressions to reuse them later. Typical examples include: parsing a floating point number, a zip code or a telephone number. (Zip code may become particularly unwieldy).

Suppose you could define a grammar for parsing floating point numbers, and then give it an alias, once defined you would be able to reuse this in regular expressions you use afterwards. In some fictional language this could look like this:

```
float := /[+-]?(\d+|\d*\.d+)(e\d+)?/
sum := /(?R<float>)+(?R<float>)/

```

This, in principle, wouldn't change anything in terms of expressive power (unless you allow self-reference), but it seems like it could make the practical implementations of regular expressions more concise?

So, my question is: has any language implemented anything like that? Or, and if not, then what would be the reason for not doing so?

# Answer
Perl 6 supports reusable regular expressions and even grammars. See http://design.perl6.org/S05.html .
> 4 votes

# Answer
Lex, the lexical analyser generator, supports this notation. In the "definitions" section, you can define patterns which you can then use in the "rules" section:

```
DIGIT    [0-9]

%%

{DIGIT}+"."{DIGIT}*  { return T_FNUM; }

```

Most lexer generators have something similar; ANTLR has "fragments", for example.
> 5 votes

# Answer
Let's start with the definition: "*A token is a string of one or more characters that is significant as a group*" ref. http://en.wikipedia.org/wiki/Lexical\_analysis

Truly, while looking for IPv6 (and related regexes) reveals that the use of *tokens to represent lexemes* is nowhere to find, even though the opportunity about that is plenty; simplicity yields compatibility though: https://www.google.gr/webhp?q=regular+expressions+ipv6#q=regular+expressions+ipv6

Obviously, using/handling the following expression requires a lexical analysis to parse it (such as *flex*):

`sum := /(?R<float>)+(?R<float>)/`

It appears that most programming languages call for a library or external tool to manage it, possibly as means to promote the more complete solutions. At least, that's our take for it today :)
> 0 votes

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


# Question
Title: Cycle of length k with no repeated edges
I need to figure out what is the minimum complexity class (L, NL, P, NPC etc..) of the following problem: Given an undirected graph G, is there exist a cycle (doesn't have to be a simple cycle) with no repeating edges, of a size at least k? (i.e. the number of edges in the cycle is at least k)

I thought that this problem can be reduced somehow to the euler cycle problem, but have no idea how to do this.

Thanks

# Answer
This problem is NP-Complete.

The $\in NP$ part is simple - guess a trail and check it.

The hardness part comes from the fact Hamiltonicity on a cubic graph is hard, as proved in Garey and Johnson book.

(In a cubic graph, every vertex-simple path walk is edge-simple, as it can not visit a vertex more than once, except maybe the start and end vertex).
> 3 votes

---
Tags: complexity-theory
---


title: Which complexity class $3^{n/3}$

text:
# Question
Title: Which complexity class $3^{n/3}$
Assuming a problem has complexity $O(3^{n/3})$,

Which is its class of complexity ?

Despite that it is not as $2^{n}$ ,we can say is an exponential ?

# Answer
> 5 votes
Yes, that is exponential. Something is exponential if it is $2^{O(n^k)}$ for some $k$. You can write $3^{n/3}$ as $2^{n\frac{\log 3}{3 \log 2}}$, so it fits.

It would be more common to write $(3^{1/3})^n \approx 1.44^n$.

---
Tags: asymptotics, landau-notation, complexity-classes
---


title: Regular expression syntax

text:
# Question
Title: Regular expression syntax
am a little confused by regular expression to convert to NFAs. am actually test using

http://www.regexr.com/

but some of regular expression like

> a\*+ab

is that mean (a\*)+ is that correct ..

also

> ab\*+bc\*

how can i get b\*+ or that mean (ab\*)+ i do not know how to get it ?

however is the (a\*)+ is the same a+ , i think will match the same ?

# Answer
> 1 votes
From the examples you give, the site you're using appears to be using "+" to mean "or". Other people use "|" for that but both notations are common enough that they can be called standard.

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


# Question
Title: ANN - Backpropagation with multiple output neurons
Can I utilize the backpropagation algorithm in a layered, feed-forward ANN in instances where there are multiple output neurons? If so, how? Links to (somewhat) comprehensible resources would be greatly appreciated, if nothing else.

The background is that I'm working on a simple C program that can create, propagate, and train dynamically sized, layered feed-forward ANNs. For the most part, everything's been going swimmingly. However, I'm having a little trouble wrapping my head around backpropogation. My main concern right now is how to use the backpropagation method for training a network that has multiple output neurons. All the examples/explanations I've found only use one output neuron. I'm *assuming* this is for the sake of simplicity. But, I'm wondering if, perhaps, this is because the backpropagation algorithm is only designed to works with one output neuron at a time. In other words, it can only be applied relative to one output neuron every time an feed-forward ANN is propagated. This would make sense, as it is known to be among the simplest ANN training methods.

Here are links to my aforesaid resources (or at least, the ones I found intuitive):

Thanks!

# Answer
> 4 votes
Backpropagation works for feed-forward ANNs with multiple output neurons.

For an output neuron $z\_r$ in an ANN, the delta function is

$$ \delta\_r = \frac{\partial f\_r(a\_r)}{\partial a\_r} e\_r\qquad, $$ where $f\_r(a\_r)$ is the activation function of $z\_r$, $a\_r$ is the sum of weighted inputs of $z\_r$ and $e\_r$ is the error of $z\_r$, $e\_r$ = $z\_r$ - $y\_r$ ($y\_r$ is the target value).

for a hidden neuron $z\_k$ the delta function is the sum of weighted deltas of the neurons in the next layer (in forward direction) of $z\_k$. So, for a neuron in the layer next to the output layer, the delta function is:

$$ \delta\_k = \frac{\partial f\_k(a\_k)}{\partial a\_k} \sum\_{r\in post(k)}\delta\_r w\_{kr}\qquad, $$

where $w\_{kr}$ is the weight between neurons $z\_k$ and $z\_r$. I suggest to have a look at the Wikipedia article about Backpropagation, especially the subsection 'finding the derivative of the error'. Following the link at the end of this section (https://www4.rgu.ac.uk/files/chapter3%20-%20bp.pdf), the first five pages or so might be helpful for a better understanding.

# Answer
> 1 votes
Training neural networks is a very broad topic. Backpropagation is just the chain rule applied in a clever way to neural networks. So yes, it deals with arbitrary networks as long as they do not have cicles (directed acyclic graphs). It is furthermore assumed that connections go from one layer to the immediately next one. It is still possible to deal with more general architectures.

A nice introductory paper is Neural networks and their applications. The book by the author is, IMHO, the best introductory text to the topic.

Particularly, if you are willing to implement it yourself, there are a number of issues you have to be aware of, which are explained in great detail. Another great resource where you will find lots of advice is the UFLDL Tutorial.

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


# Question
Title: Are two non-Turing-recognizable languages closed under union?
If I have two languages that aren't Turing-recognizable, is the union between them always not T-recognizable? Why?

# Answer
No, sometimes you can recognize their union. As an example, take a language where it and its complement are undecidable. Then their union is decided by a TM that always says yes.
> 8 votes

# Answer
Let $U\subseteq \mathbb{N}$ be any unrecognizable set. Let $L\_1 = \\{0, 2, 4, \dots\\} \cup \\{2n+1\mid n\in U\\}$ and $L\_2 = \\{1,3,5, \dots\\} \cup \\{2n\mid n\in U\\}$. $L\_1$ and $L\_2$ are both unrecognizable but their union is $\mathbb{N}$.
> 11 votes

---
Tags: turing-machines
---


title: Kleene closure, concatenation problem

text:
# Question
Title: Kleene closure, concatenation problem
If $L\_1 = \emptyset$ , $L\_2= \\{a\\}$ then what is $$L\_1\cdot L\_2^\* \cup L\_1^\*$$

The answer given is $\\{\epsilon\\}$ but I think it should be $\\{\epsilon,a\\}$. My Approach :
$L\_1^\* = \\{\epsilon\\}$
$L\_2^\* = \\{\epsilon,a\\}$
$L\_1\cdot L\_2^\* = \\{\epsilon,a\\}$
$L\_1\cdot L\_2^\* \cup L\_1^\* = \\{\epsilon,a\\}$.

Where's my mistake?

# Answer
For any language $L$, $$\emptyset⋅L=\emptyset$$.

Therefore, $$L\_1\cdot L\_2^\* = \emptyset \cdot L\_2^\* = \emptyset$$

And thus $$L\_1\cdot L\_2^\*\cup L\_1^\* = \emptyset \cup L\_1^\*= L\_1^\* = \\{\epsilon\\}$$.
> 2 votes

# Answer
Your problem is in applying the definitions of the concatenation and Kleene-star operators. The exercise was probably deliberately chosen to test your understanding of the difference between $\emptyset$ (the language containing no strings at all) and $\\{\epsilon\\}$ (the langauge containing only the empty string), and how the operators apply to them, but you also tripped up on $\\{a\\}^\*\\!$.

* For any language $L$, $L^\*$ is the language formed by taking zero or more strings from $L$ and concatenating them. In particular, if $L=\emptyset$, the only way that you can choose zero or more strings from $L$ is to choose none. If you start with no characters and concatenate nothing, you still have no characters: the empty string. So $L\_1^\* = \emptyset^\* = \\{\epsilon\\}$. On the other hand, if you start with $L\_2=\\{a\\}$ and choose zero or more strings from that language, you have chosen zero or more $a$s. Therefore, $L\_2^\* = \\{a^n\mid n\geq 0\\} = \\{\epsilon, a, aa, aaa, \dots\\}$.
* For any languages $L$ and $L'\\!$, $L\cdot L'$ is the set of all strings that can be made by choosing one string from $L$ and one from $L'$ and concatenating them. You can never choose a string from the empty language, so you can never make any strings by concatenating something in $\emptyset$ and something in $L2^\*$, so $L\_1\cdot L\_2^\* = \emptyset\cdot L\_2^\* = \emptyset$.

So the answer is $\emptyset \cup \\{\epsilon\\} = \epsilon$.
> 2 votes

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


# Question
Title: Min-Max number of shifts and reductions in bottom-up parser
Given the Grammar has no unit or ɛ-productions,
What is minimum & maximum number of shifts and reduce needed by bottom-up parser?

# Answer
I first assume that you are considering deterministic parsing. Other tpes of parser can mimic shift-reduce in a non-derterministic context.

Assuming the there is no unit production, and no $\epsilon$-production. The maximum number of reduce is precisely the number $k$ of non-leaf (non-terminal) nodes in the parse tree, i.e. the number of productions rules used to generate the string parsed.

This number is maximum when the grammar is in binary form, i.e. with right-hand sides (rhs) of length 2 (it does not have to be in Chomsky Normal Form). Then the parse tree is a binary tree. The number of non-leaf nodes is then $n-1$ when n is the length of the parsed string.

If the maximum length for a rhs of a rule is $p$, assuming it is possible to generate a terminal string of length $n$ with only such productions, then $n=k\*(p-1)+1$. So the minimum number of reduce is $k=(n-1)/(p-1)$. This formula could have been used in the binary case too.

In other words, you consider the least branching tree (binary) and the most branching tree to estimate upper and lower bound to the number of reduce.

Since the shift is pushing an input symbol on the stack, the number of shifts is the length $n$ of the string being parsed.

A document with definitions: Introduction to Shift-Reduce Parsing

## Proof of the formula

We want to show that if a tree has all nodes with $p$ daughters, we have the formula $n=k\times(p-1)+1$ where n is the number of leaf nodes, and k is the number of non-leaf nodes.

The proof goes by induction on the number $k$ of non-leaf nodes.

* Base case: $k=0$ (no non-leaf node)
The tree is reduced to a single leaf node. Thus $n=1$. The formula is verified trivially.
* induction case: We suppose the formula verified for all trees with less than $k$ non-leaf nodes.

Consider a tree $T$ with $k$ non-leaf nodes. Consider a maximal path from the root of $T$ to any of its leaves. Let $U$ be the last non-leaf node on that path. All daughters of $U$ are necessarily leaf nodes, because otherwise there would be a longer path to a leaf. If you remove the subtree rooted in $U$ and replace it with a leaf $u$, you have a tree with $k'=k-1$ non-leaf nodes, but you have lost $p$ leaf nodes that were dauthers of $U$ and gained one which is $u$. Hence the number of leaves is $n'=n-p+1$.

Since $k'\<k$, by induction hypothesis, the tree satisfies the formula $n'=k'\times(p-1)+1$

Hence $n-p+1=(k-1)\times(p-1)+1$.

Hence $n=(k-1)\times(p-1)+1+(p-1)$, from which we get the formula for the original tree $T$ with $k$ non-leaf nodes: $n=k\times(p-1)+1$

So the formula is verified for any tree where all nodes have $p$ daughters.

This proof is valid for all values of $p$ such that $p\>0$

The formula is of course applicable to parse trees when all rules have a right-hand side of length $p$, which means $p$ daughters for each node in the parse tree. It even works if you have only unary rules (but is not very useful).

In te case of binary rules, you have $p=2$ and the formula becomes: $n=(k\times(2-1)+1$, i.e. $n=k+1$. Hence the number of non-terminals is $k=n-1$ where n is the number of terminals.

This could be extended to RHS with different sizes, but it would be more complex to write.
> 2 votes

# Answer
The number of shifts is always precisely the number of symbols in the input stream, since every symbol is shifted exactly once. The number of reductions depends on the grammar; it is impossible to answer that question without knowing something about the grammar.

For example, if the grammar were in Chomsky Normal Form, you could easily count the number of reductions because for CNF grammars, the concrete syntax tree must be a complete binary tree and each node in the tree corresponds to a single reduction.
> 2 votes

---
Tags: compilers, parsers, syntax-trees
---


title: What happens when thread is created

text:
# Question
Title: What happens when thread is created
When working on Linux what happens when a thread is created? It is a separate execution flow. Does each thread have their own code section? Personally I don't think threads would be able to share code section even if it's the same section. Say if the number of threads being created is dynamic. How is the memory allocated for each thread? Will the memory foot print, especially code section, increase as threads are created?

# Answer
(Although you asked about Linux, which would be off-topic, the same principles apply on most operating systems, and general principles are on-topic here.)

Threads share their code section. In many systems, even separate tasks that are executing the same program can share their code section, because the code sections are read-only, so whatever one task does won't affect the other task. I don't know how to explain this better because you don't say why you don't think it would be possible. It is possible, and it's routinely done.

Each thread has its own set of register values, including the program counter. Each thread also has its own call stack. Having its own program counter and call stack (in a way, the program counter is the top of the call stack) pretty much defines a thread. Multiple threads of the same task have program counters that each point at some place in the shared code section.

Creating a thread requires allocating memory to store its stack, and to store its register values when switching between threads. It doesn't affect the code section.
> 5 votes

---
Tags: threads
---


# Question
Title: Minimal complexity for pairing two comparable sets with comparability restrictions
A project at university (whose deadline has passed by now) presented the following problem:

> Consider two finite sequences of (not necessarily distinct) real numbers $a\_1,\ldots,a\_n$ and $b\_1,\ldots,b\_n$ such that the $b\_k$'s are a permutation of the $a\_k$'s. The aim is to create an algorithm which returns a permutation which maps the sequence $(a\_k)$ onto $(b\_k)$. In order to find such permutation it is necessary to compare some numbers during the algorithm. The restriction is that one cannot compare any $a\_x$ with an $a\_y$ or a $b\_x$ with a $b\_y$: all that is allowed is to compare a number of the first sequence with one of the second sequence.

I am wondering what would be the minimal (worst-case) complexity of the number of comparisons. It's not hard to get $O(n^2)$: for every $a\_x$, search brute-force for a corresponding $b\_y$, which costs $O(n)$ comparisons giving a total of $O(n^2)$.
A bit smarter would be to adapt the familiar QuickSort algorithm, in the recursions step taking as a pivot a couple $(a\_x,b\_y=a\_x)$ (which can be found in $O(n)$ comparisons) and partitioning both sequences using this 'pivot'. This gives $\Theta(n\log n)$ comparisons in average, but still $\Theta(n^2)$ worst-case (as usual with QuickSort).

It's not hard to see that $\Omega(n\log n)$ is a minimum: represent a given algorithm as a binary decision tree with a comparison at each node. Since the total number of leaves can reach $\Theta(n!)$ (the number of permutations in case all the $a\_k$ are different) the height of the tree is at least $\Omega(\log\_2(n!))=\Omega(n\log n)$.

It seems likely that a $O(n\log n)$ algorithm exist, but I have not been able to find one. I have tried adapting MergeSort, but a problem during the merging arises giving a worst-case of $\Theta(n^2)$ nonetheless.

Is this a known problem? Does a $O(n\log n)$ algorithm exist? Do you have suggestions for other known sorting algorithms which might be adapted without increasing their complexity?

# Answer
This is the famous "nuts and bolts" problem. Yes, there is a randomized algorithm with expected running time $O(n \lg n)$, using a QuickSort-like algorithm.

The problem is famous because there is a simple *randomized* algorithm that achieves $O(n \lg n)$ expected running time. However, it's very challenging to find a *deterministic* algorithm with a $O(n \lg n)$ time running bound. Therefore, it makes a nice illustration of the utility of randomness.

The problem is described in several algorithms textbooks, including CLRS and Skienna's textbook.
> 1 votes

---
Tags: algorithms, complexity-theory, sorting
---


# Question
Title: What happened if we implement quicksort without tail recursion?
On Wikipedia, it said that

> The in-place version of quicksort has a space complexity of $\mathcal{O}(\log n)$, even in the worst case, when it is carefully implemented using the following strategies:
>
> > * in-place partitioning is used
> > * After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most $\mathcal{O}(\log n)$ space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack.

Below is naive quick sort:

```
Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

```

Below is tail recursion quick sort:

```
Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

```

Algorithms above are based on this link

What if we just use in place partitioning? Is it not enough to make quicksort having space complexity of $\mathcal{O}(\log n)$?

Below is what I understand of stack call of quicksort. Do I misunderstand it?

Suppose I have sequence of number: $\\{3, 5, 2, 7, 4, 1, 8, 6\\}$. I use in place method in this case.

```
input    : 5   3   2   7   4   1   8   6
partition: 3   2   4   1  (5)  7   8   6
stack 1  : 2   1  (3)  4
stack 2  : 1  (2)
stack 3  : 1                               - stack 3 removed
stack 2  : 1  (2)                          - stack 2 removed
stack 1  : 1   2  (3)   4
stack 2  :              4                  - stack 2 removed
stack 1  : 1   2  (3)   4                  - stack 1 removed
input    : 1   2   3   4  (5)  7   8   6
stack 1  :                    (6)  7   8
stack 2  :                        (7)  8
stack 3  :                             8   - stack 3 removed
stack 2  :                        (7)  8   - stack 2 removed
stack 1  :                    (6)  7   8   - stack 1 removed
input   : 1   2   3   4   5   6   7   8 -> sorted

```

We need $3$ stacks at most, which is $$\log(n) = \log(8) = 3$$

If what I told above is correct, the worst case with that method is $n$, which is happened when the pivot is the minimum or maximum

```
input    : 5   3   2   7   4   1   8   6
stack 1  :(1)  5   3   2   7   4   8   6
stack 2  :    (2)  5   3   7   4   8   6
stack 3  :        (3)  5   7   4   8   6
stack 4  :            (4)  5   7   8   6
stack 5  :                (5)  7   8   6
stack 6  :                    (6)  7   8
stack 7  :                        (7)  8
stack 8  :                             8
stack 7  :                        (7)  8
stack 6  :                    (6)  7   8
stack 5  :                (5)  6   7   8
stack 4  :            (4)  5   6   7   8
stack 3  :        (3)  4   5   6   7   8
stack 2  :    (2)  3   4   5   6   7   8
stack 1  :(1)  2   3   4   5   6   7   8
input    : 1   2   3   4   5   6   7   8 -> sorted

```

we need $8$ stacks, which is $n$

That's why in place partitioning is not enough. But if I am correct, what makes it different using tail recursion?

And also, anyone can give pseudo code for iteration instead of tail recursion?

# Answer
> 2 votes
You're correct that your version with a loop doesn't guarantee O(log n) additional memory. The problem is that you have recursively sorted the partition "on the left". You ignored:

> the partition **with the fewest elements** is (recursively) sorted first

This is essential. It ensures that each time you make a recursive call (and lay down a new stack frame, requiring constant additional memory), the sub-array that you are sorting is at most half the size of sub-array being sorted at the previous stack level. Therefore the maximum depth of the recursion is the base-2 `log n`, which gives the desired bound on memory use.

In your code you permit a worst case in which you recursively sort the larger partition, having size only one smaller than the previous at each step. Then indeed the recursion depth can be `n`.

The way to make the code entirely iterative, with no call-recursion at all, is (as always) to use a stack data structure instead of the call stack. So instead of recursively calling to sort the small partition, you push the *large* partition on to the stack (by which I mean, push a pair of integers describing its location in the array) and loop around to continue sorting the *small* partition. When the size of the piece you're working on hits 1 you pop the stack and loop around to continue sorting that.

# Answer
> 1 votes
Below is an iteration-based quicksort proposed by Leslie Lamport. You can find it in this video lecture (title: Thinking for Programmers, from time: 32:35).

The basic idea is summarized as follows.

Initially, there is only an entire array. The first application of `partition` results in two subarrays. When the two subarrays are sorted separately and in place, the entire array is sorted. The second `partition` will divide one of the two subarrays into two smaller subarrays. Continuing on this, we obtain more and more subarrays with less and less elements to be sorted. Each of the smallest subarrays contains a single element and is sorted by default. In this way, we obtain an iterative quicksort algorithm.

```
Algorithm quick-sort-iter(A:array, lo:int, hi:int)
    @state
    range_array is an array (we use FIFO queue) of subarrays to be sorted;
    each subarray is a triple of `(A, lo, hi)`.

  range_array := {(A, lo, hi)}

  while (range_array is not empty)
  {
    (A, lo', hi') := pop (and remove) a subarray from range_array
    if (lo' < hi')
    {
      p := partition(A, lo', hi)
      range_array := range_array + {(A, lo', p - 1), (A, p + 1, hi')}
    }
  }

```

# Answer
> 1 votes
No, it is not, because the recursive calls can go deeper than $log(n)$ in the worst case (they can atually go as deep as $O(n^2)$) and if you don't use tail-recursion then your computer needs to store the state at every level of recursion, because it will return to every level later. Tail reursion guarantees your computer that it does not need to store the data from every recursion level, because it will never get back to those levels anyway (as the recursive call should be exactly the last thing done in a tail-recursive method.)

---
Tags: algorithm-analysis, space-complexity, quicksort
---


# Question
Title: If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?
> $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$
> $T(1)=1$
> The value of $T(m^2)$ for m ≥ 1 is?

Clearly you cannot apply master theorem because it is not of the form $T(n)=aT(\frac{n}{b})+f(n)$
So I tried Back Substitution:
$T(n)=T(n-1)+\lfloor\sqrt{n}\rfloor$
$T(n-1)=T(n-2)+\lfloor\sqrt{n-1}\rfloor$
therefore,
$T(n)=T(n-2)+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(n-3)+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(n-(n-1))+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(1)+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(1)+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
I'm stuck up here and the answer is given as -

> $T(m^2)=\frac{m}{6}(4m^2 - 3m + 5)$

how to solve and reach the answer?

# Answer
Your problem is that you're ignoring the floors. Make sure that you know what $\lfloor x \rfloor$ means.

It is not hard to check that $$ T(n) = \sum\_{k=1}^n \lfloor \sqrt{k} \rfloor. $$ Therefore $$ \begin{align\*} T(m^2-1) &= \sum\_{k=1}^{m^2-1} \lfloor \sqrt{k} \rfloor \\ &= \sum\_{r=1}^{m-1} \sum\_{\ell=r^2}^{(r+1)^2-1} \lfloor \sqrt{\ell} \rfloor \\ &= \sum\_{r=1}^{m-1} \sum\_{\ell=r^2}^{(r+1)^2-1} r \\ &= \sum\_{r=1}^{m-1} \[(r+1)^2-r^2\] r \\ &= \sum\_{r=1}^{m-1} (2r+1)r \\ &= \sum\_{r=1}^{m-1} 4\binom{r}{2} + 3\binom{r}{1} \\ &= 4\binom{m}{3} + 3\binom{m}{2}. \end{align\*} $$ Therefore $$ \begin{align\*} T(m^2) &= 4\binom{m}{3} + 3\binom{m}{2} + m \\ &= \frac{4m(m-1)(m-2)}{6} + \frac{3m(m-1)}{2} + m \\ &= \frac{(4m^3-12m^2+8m) + (9m^2-9m) + (6m)}{6} \\ &= \frac{4m^3-3m^2+5m}{6}. \end{align\*} $$
> 2 votes

# Answer
For a slightly different way to look at his problem, consider your original equation, $$ T(n) = T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor+\dotsb+\lfloor\sqrt n\rfloor $$ Now the key here is to group the terms with the same values of $\lfloor\sqrt k\rfloor$: $$\begin{align} T(n) &= (T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor)\\ &+(\lfloor\sqrt4\rfloor+\lfloor\sqrt5\rfloor+\lfloor\sqrt6\rfloor+\lfloor\sqrt7\rfloor+\lfloor\sqrt8\rfloor)\\ &+(\lfloor\sqrt9\rfloor+\lfloor\sqrt{10}\rfloor+\lfloor\sqrt{11}\rfloor+\lfloor\sqrt{12}\rfloor+\lfloor\sqrt{13}\rfloor+\lfloor\sqrt{14}\rfloor+\lfloor\sqrt{15}\rfloor)\\ &+\dotsc \end{align}$$ and observe that each summand will have $2k+1$ terms, since the difference $(k+1)^2-k^2 = 2k+1$: $$ T(n) = (1\cdot3)+(2\cdot5)+(3\cdot 7)+(4\cdot 9)+\dotsb $$ so we'll have, with $n=m^2$ $$\begin{align} T(m^2) &= (1\cdot3)+(2\cdot5)+\dotsb+\left(\left\lfloor\sqrt{(m-1)^2}\right\rfloor+\dotsb+\left\lfloor\sqrt{m^2-1}\right\rfloor\right)+\left\lfloor\sqrt{m^2}\right\rfloor\\ &=\sum\_{k=1}^{m-1}k(2k+1)+m =\sum\_{k=1}^{m-1}(2k^2+k)+m\\ &=2\sum\_{k=1}^{m-1}k^2+\sum\_{k=1}^{m-1}k+m\\ &=2\frac{(m-1)(m)(2(m-1)+1)}{6}+\frac{(m-1)(m)}{2}+m\\ &=\frac{m}{6}(4m^2-3m+5) \end{align}$$ as required.
> 3 votes

---
Tags: asymptotics, recurrence-relation, recursion
---


title: Kleene star and Kleene plus

text:
# Question
Title: Kleene star and Kleene plus
Let $\Sigma$ be an alphabet. Have a look at following definitions frequently used in literature containing Kleene star and Kleene plus.

$\Sigma^\* := \Sigma^+ \cup \\{\varepsilon\\}$
$\Sigma^+ := \Sigma^\* \setminus \\{\varepsilon\\}$

These definitions lead to different sets iff $\varepsilon \in \Sigma\_i$ for some $i$. What's the proper one in general context? Is it similar to mathematical issues like multiplicative identity in rings or including zero in the set of natural numbers?

# Answer
$\Sigma$ is a finite set of elements called *letters*. A *word* is a sequence of 0 or more letters. For every alphabet, there is a unique 0-letter word called the empty word, denoted $\epsilon$. By definition, $\epsilon\notin \Sigma$, for eny $\Sigma$.

Thus, $\Sigma^\*$ and $\Sigma^+$ are both well defined, and are used for different purposes.

Mathematically, $\Sigma^\*$ with the concatenation operation is a monoid, with $\epsilon$ being the identity element. $\Sigma^+$ is thus a semi-group, with the concatenation operation, as it doesn't have an identity element.
> 7 votes

---
Tags: formal-languages
---


title: Flowcharts vs DFA resp FSM equivalency

text:
# Question
Title: Flowcharts vs DFA resp FSM equivalency
First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I am a bit confused about this. There are classes where using logical synthesis, Karunaugh maps, state encodings, flip flops etc. one is able to construct hardware consisting of logic gates and flip-flops which realizes the desired DFA. Basically all processes that runs on the computer (no matter if is written in C# or Assembler), are at the lowest level realized through logical gates, zeros and ones. So it seems that programs firstly needs to be converted (by compiler I suppose) to some form as I've described. This might imply that every problem that is solvable using C# is solvable using FSM. But this is in contradiction to Chomsky hierarchy and all this theory related stuff, which says that you cannot do the same magic with regular expressions (which are based on FSM) that you can do on Turing machine (which is equivalent of any programming language, if I am wrong correct me please). Moreover, if flowcharts (or even C#, Java ... source codes) were equivalent to FSM why we do not have all software formally verified so far? There is mathematical apparatus for FSM and related stuff, so why do not formally verify everything and ensure the correctness? What I am missing here?

# Answer
> 3 votes
Converted comments to answer.

FSM is an ambiguous term but is often taken to mean "finite automaton", of which deterministic finite automata (DFAs) are representative. These are strictly less powerful than Turing machines and other Turing-equivalent systems of computation. That said, actual computers running C# programs are not Turing equivalent; in fact, they're a strictly weaker model of computation that finite automata, although many interesting finite automata can be modeled exactly, and many Turing machines can be simulated accurately. PC \< FSM ~ DFA \< TM.

Suppose that your PC has 1 TB of memory (RAM, registers, stack, HDD, etc.) This is 8796093022208 bits. Your computer can exist in 2^8796093022208 unique states. It is therefore incapable of recognizing any regular language whose minimal DFA contains more than 2^8796093022208 unique states. One such language is the language containing the first 2^8796093022208 words over a unary alphabet (when ordered lexicographically).

# Answer
> 1 votes
As Patrick87 mentions, FSMs could mean several things, depending on context. They can be used to refer to DFAs, to NFAs, and perhaps even to PDAs. Flowcharts are something different altogether. They describe the flow of control in a computer program. They can be used either informally, say when describing an algorithm, or formally, say to do static analysis in a compiler. In the latter case they are a (possibly annotated) directed graph. DFAs and NFAs are also annotated directed graph, but the semantics are different. DFAs and NFAs have a very specific semantics that describes how to execute them. Flowcharts are an abstraction of some features of the computation, but don't necessarily describe it fully; when they do, they are usually more expressive than FSMs. Indeed, FSMs are read sequentially, each edge consuming one input symbol. In contrast, flowcharts describe arbitrary instructions. The input is consumed at will, perhaps even at random order.

In contrast to Patrick87's answer, I see no reason to read flowcharts with a real machine in mind. Flowcharts usually make sense for an abstract machine whose variables and memory are unbounded, and in that sense they are a representation of a Turing-complete computation model, though perhaps an incomplete representation. They are more powerful then FSMs. For example, you can consider the following flowchart, with four states S, END, YES, NO and the following informally described transitions:

1. There is an "initial" transition pointing at S annotated "$x=y=z=0$".
2. There is a self loop at S annotated "read $a$; increase $x$".
3. There is a self loop at S annotated "read $b$; increase $y$".
4. There is a self loop at S annotated "read $c$; increase $z$".
5. There is an edge from S to END annotated "end of input".
6. There is an edge from END to YES annotated "$x=y=z$".
7. There is an edge from END to NO annotated "otherwise".

This is similar to an FSM since it does consume one character at a time. However, the side effects are different since variables are kept, and the language computed by the machine is not context free (can you figure it out?). Flowcharts are even more general since they don't have to read a character at every step.

Summarizing, both FSMs and flowcharts are described by annotated directed graphs. That's a common modelling device, but it exhausts the connection between the models.

---
Tags: formal-languages, turing-machines, finite-automata, computer-architecture
---


# Question
Title: Analysing Algorithms Big Oh/Complexity theory
I'm revising for my finals and from looking at previous exam papers I have a found a popular question that has came up almost every year, worth a lot of marks. Each year the question is written very similar with minor changes. I've not really been good at analysing algorithms this semester, so I was hoping based on the questions you guys could provide some resources links to specific things that'll help me learn to understand these type of questions. It'd help me a ton come the exam.Thanks.

I'M NOT EXPECTING ANY OF YOU GUYS TO WORK THESE OUT, JUST POINT ME IN A DIRECTION OF RESOURCES THAT'LL HELP ME OUT. As I'm really struggling with understanding, i have been through my notes provided by college but it hasn't really helped.

# Answer
> 0 votes
I'm not sure I can provide any links, but here is the gist of it. The number of iterations in the inner loop in the first version is $$ \sum\_{i=1}^Z \sum\_{j=n^2-X\_i}^{n^2+Y\_i^2} 1 = \sum\_{i=1}^Z (Y\_i^2 + X\_i + 1). $$ This is going to be smallest when $Z,X\_i,Y\_i^2$ are smallest, and largest when they are largest. To see just how small or how large, you need to perform some calculation. The smallest sum, for example, is attained for $Z = 1$, $X(1) = 0$ and $Y(1) = 1$, in which case it is $2$. The question actually asks you to count basic operations, and that depends on your set of basic operations; but it can only affect the result up to a multiplicative constant.

# Answer
> -1 votes
First of all think about the operations perform in each loop. For example, let's look at the first problem this way. Assume `Array.length` is 5, so $1\le i,z\le 5$ (taking the array to start at $1$).

```
X(i) =1^2, 2^2, ....5^2 ={1,4,9,16,25},
 Y(i) = 1^4, 2^4,....5^4 ={1,16,81,256,625}

for int i = 1 to Array.length
   for int j = n^2-X(i) to Y(i)^2 + n^2
            k = 0;

```

when z = 5, X(5) = 25, Y(5)= 625, so the inner loop looks like this

```
        for int j = 0 to 625^2 + 25; // 25-25 to 625*625 + 25
                  k = 0;

```

you can see that the inner loop dominates, n^4 + n^2, so the two loops combined look like n(2(n^4 + n^2)) or 2(n^5 + n^3). Notice that K = 0 is evaluated n^4+n^2 times leading to the 2(n^4+n^2). Therefore the worse case time complexity is 2(n^5 + n^3) or just O(n^5), always consider the dominant term in the polynomial. I recommend you always make up some values, plug them into the loops variables and see what shows up. I hope this helps.

Here is link to some examples you can also look at. http://www.cs.sfu.ca/CourseCentral/225/johnwill/cmpt225\_4onotation.pdf. Good luck with your finals.

---
Tags: algorithms, java
---


# Question
Title: Unsplittable flow in capacitated networks
I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be routed without capacity violations.

This problem seemed to be similar the classical unsplittable flow problem (UFP). However, I am not really interested in routing as many flows as possible. I rather want a solution where all flows are routed without violations or I will recompute different demands and try again.

Since this is just part of a bigger heuristic I am building, I was looking for fast and easy to understand algorithms that I could implement. I read some papers and presentations on the UFP (e.g. this). Unfortunately, in the algorithm description (slide 22) it doesn't descirbe how the possible paths are searched for and how the flow is routed.

I would be thankful for some fast and simple algorithms to solve my problem. If the UFP is not as similar as I thought, I am also glad to learn about new more applicable problem models.

I also thought about calculating the shortest paths using Dijkstra's algorithm while also updating the capacities. But that might not always find solutions, even if it is a feasible problem, i.e. when the order of the routed flows is of matter. Also, I'm not sure if this is a very efficient way.

# Answer
The easiest algorithm to implement will probably be to use integer linear programming, and then use an off-the-shelf ILP solver. I would suggest starting with that and seeing if it is efficient enough, and only dive into the literature if ILP does not meet your needs.

One formulation as ILP could go something like this. For each edge $e$ and each source $s$ you have a variable $f\_{e,s}$ that indicates how much flow from source $s$ goes through edge $e$. You'll have a constraint saying that $\sum\_s f\_{e,s}$ has to be at least the demand and at most the capacity, for each edge $e$. Also, you'll have a constraint representing conservation of flow.

Finally, to encode the unsplittable flow condition, for each edge $(v,w) \in E$ and each source $s$, add a variable $x\_{v,w,s}$ that is $1$ if the flow from $s$ enters $v$ and goes next to $w$, or 0 otherwise. To ensure that no flow splits, you'll have a constraint $\sum\_w x\_{v,w,s} \le 1$ for each $v,s$ and a constraint $f\_{(v,w),s} \le K \cdot x\_{v,w,s}$, where $K$ is a huge constant.

This should be relatively easy to implement. You can formulate some code to produce the right ILP system in an hour or two, and then use an off-the-shelf ILP solver. Therefore, you should be able to very quickly experiment with this approach and see whether it meets your needs or not, before diving into the research literature on multi-terminal unsplittable flow problems.
> 1 votes

---
Tags: algorithms, computer-networks, heuristics, network-flow, routing
---


# Question
Title: Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine
If I have some non-deterministic Turing machine $NDTM$ running some process $Q$ and I wish to simulate the same process $Q$ with a deterministic single-tape Turing machine $DTM$, there will of course be an exponential slowdown. However, what penalty can one expect in terms of space resources? Unless one has access to an $RNG$, presumably one has to keep track of which configurations one has already tried? Can we simulate the $NDTM$ with the $DTM$ using only polynomially more space?

# Answer
Savitch's theorem shows that $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{SPACE}(f(n)^2)$.
> 1 votes

---
Tags: turing-machines, space-complexity, nondeterminism
---


title: Big Omega of 3-Sum Algorithm

text:
# Question
Title: Big Omega of 3-Sum Algorithm
An optimized algorithm for the 3-sum problem with an input array `N` has `O(N^2logN)` however I read that the Big Omega for this algorithm could be Omega(N) because you have to touch all entries once. But to me this doesn't make sense.

If you have to perform the 3-sum operation on the entire array, wouldn't Big-O and Big-Omega be the same because regardless of the results the algorithm has to perform the same operations on the entire array?

# Answer
We don't know what the best complexity for the 3SUM problem is. First of all, we can improve on your $O(N^2\log N)$ algorithm to an $O(N^2)$ algorithm by carefully scanning the two arrays in tandem, thus obviating the binary search. Until very recently, it had been conjectured that there is a corresponding $\Omega(N^2)$ lower bound, and on this basis the complexity of many other problems, especially in computational geometry, had been "determined". However, very recently Grønlund and Pettie gave an $O(N^2/(\log N/\log\log N)^{2/3})$ algorithm, so we know that the $O(N^2)$ algorithm is not optimal. It is still conjectured that 3SUM requires $\Omega(N^{2-\epsilon})$ time for every $\epsilon \> 0$.
> 1 votes

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


# Question
Title: How does time/space complexity work with lisp
I'm completely new to programming but I've had a course in computational complexity. I'm trying to read the book "Structure and Interpretation of Computer Programs." In the first few sections, the authors make some claims about the relative efficiency of tree recursive and iterative processes. I find it a little frustrating that they don't formalize exactly what that mean by the run time of a program. They do mention that the interpreter uses applicative order evaluation. The problem is that it's still not totally clear what counts as one "step" of the process. For instance if one uses applicative order to evaluate the the 5th element in the sequence of Fibonacci numbers using the tree recursive algorithm fib(n)=fib(n-2)+fib(n-1), one gets

(Fib 5)

(+ (fib 4) (fib 3))

(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))

(+ (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0)) 1))

(+ ( + (+ (+ (fib 1) (fib 0)) 1) (+ 1 1)) (+ ( + 1 1) 1))

(+ ( + ( + ( + 1 1) 1) 2) ( + 2 1))

(+ (+ (+ 2 1) 2) 3)

(+ (+ 3 2) 3)

(+ 5 3)

8

So there are ten steps, and in general fib(n) will take 2n steps: n to get to the bottom of the tree, and n to come back up. It's claimed, however, that the run time is asymptotic to fib(n). I can sort of see intuitively why this is true; the number of times in the process that two numbers are added together is clearly about fib(n), but I was hoping there is a more exact definition of run time. Any help is appreciated.

# Answer
You get the fib(n) running time if you only expand one invocation of fib at a time. You haven't been told the exact execution model for several reasons:

1. It is messy.
2. It's not important.
3. It could depend on the implementation.
4. You need to worry about low-level stuff such as the complexity of integer operations.

The reason it's not important is that when measuring complexity we only care about the order of growth of the number of operations. So if a certain basic operation takes 3 or 13 units of time, it makes no difference for us.
> 1 votes

---
Tags: lisp
---


title: Termination in infinite-time

text:
# Question
Title: Termination in infinite-time
Does it make sense to speak of algorithms that take an infinite amount of time to terminate?

In particular, suppose we have a loop with a bound function that is initially positive and is decreased by the loop body each time. Furthermore, suppose that termination of the loop implies that bound function is non-positive. (Ie almost all assumptions of The Invariance Theorem are satisfied.)

Here's the rub, initially the value of the bound function is the cardinality of the natural numbers.

What can be said in such situations?

Any help or direction is most welcome; thank you!

# Answer
A big thing that is studied in higher type computability is infinite streams. Others have talked about hyper computation but this isn't quite the same. For starters the objects and functions studied in higher type computability are all things you can do in Haskell or some other such real programing language. These functions DO terminate in finite time thanks to laziness.

Exact real arithmetic is arithmetic that is performed on infinite binary streams or other kinds of infinite streams (dyadic digits and more commonly having both negative and positive digits). Addition of such streams terminates in finite time but produces another object which is infinite. The trick here is that the infinite streams are definable by computable functions that have finite construction. It turns out that classically there exist certain infinite streams that we can't define. For instance a computable real on the range $\[0, 1\]$ can be defined by a function $f : Nat \to Bool$. If we have an undecidable set $S$ then if we consider $f(x) = 1$ if and only if $x \in S$ then $f$ defines a real number but NOT a computable real number. It seems to turn out that there are no natural examples of such numbers coming up in practice however.

For more information take a look at one of my favorite blog posts: seemingly impossible functional programs
> 4 votes

# Answer
What you are describing is a notion of hypercomputation. Several ways of making sense of infinite computation are described in the Wikipedia article on hypercomputation. The approach of Hamkins and Lewis seems particularly popular. There is no need to invoke a cardinal-valued variable though; you can just have a plain old infinite loop.
> 3 votes

# Answer
Yes, there are plenty of models of computation on infinite data where computations go on forever. For example, ordinary finite automata can be adapted to deal with infinite strings, giving $\omega$-automata.

However, it doesn't make sense to talk about such computations *terminating* since terminate means "end" and an infinite computation doesn't do that. So the acceptance criterion for an $\omega$-automaton isn't as simple as "It accepts if it terminates in an accepting state". There are various ways of doing this. Conceptually, the easiest is the Büchi automaton, which accepts its infinite input if it visits accepting states infinitely often.
> 3 votes

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


# Question
Title: Why do most scientists believe that P≠NP?
I read that most scientists don't believe that P=NP. It might be subjective but can you simplify why not? I'm not informed enough to have an opinion but I'd like to know the definitions and some "pretty simple" explanation why to believe one or the other case, for instance why even believe that it can be proved?

# Answer
> 9 votes
An NP-complete problem can be transformed into another NP-complete problem. There's an abundance of known NP-complete problems, in fact, one could even say that any really interesting problem is NP-complete. So if you know of a way of solving *any* NP-complete problem $X$ quickly, you can take any other NP-complete problem, transform it into an instance of $X$, and solve that quickly as well.

Several smart researches have spent a lot of time on researching these hard problems. Despite all the efforts and years, we still don't have a polynomial time algorithm for any of the NP-complete problems. We also have conditional results of the form "if you can do this faster/better, then P=NP".

As for proving the claim, we don't perhaps know much for sure. What we do know is that whatever the proof looks like, it can't be of a certain type. So at least if there ever was a proof, it will have to address how it avoids some known difficulties.

For more details, you could first have a look at Sipser's book, and then the Arora-Barak book.

# Answer
> 3 votes
P≠NP seems to be a sort of "computational speed limit" or "no free lunch theorem" or "fundamental bottleneck" of which there are many other similar examples from many branches of science, mathematics, and even physics. the amount of computation required to solve a SAT problem is exponential in all known algorithms, and there are many that have been invented over the years by top researchers. decades of research have gone into solving SAT alone, in fact over ½-century of research eg since the Davis Putnam algorithm which was found and analyzed in ~1960 even a decade before the theory of NP completeness in the early 1970s.

intuitively P≠NP states that no matter how brilliantly creative the algorithm designer is, there are fundamental limits in improving the efficiency of code. in this way it even has parallels to physical laws eg thermodynamics. its can be interpreted as a limit on the amount of information processing that can be done per time by *any* physical system.

but, no one thinks there is a "pretty simple" reason the theorem is true, at least in the sense of proof structure, because if such a reason existed, it seems like it would be discovered by now. in other words it seems to be true but the reason is "extremely complicated". possibly from a few decades of future research and analysis/simplification *after* it is proved, it might start to look "simpler" in 20-20 hindsight/retrospect, some proofs esp critical ones go through that somewhat evolutionary process over time.

another angle on this is that modern cryptography is based on the existence of "hard" functions and "trapdoor" type functions in which computation is easy in one way and not the other. in other words researchers are so confident in the belief that P≠NP they've built elaborate cryptographic systems based on the premise.

however, a small minority of researchers "dont rule out" P=NP some of them accomplished experts, eg RJ Lipton.

> One of the reasons for these posts is that I believe that much of what we believe as a community about P$\stackrel{?}{=}$NP may be at best guesswork and at worst just plain wrong. Most think that “obviously” P≠NP, yet I am not so sure. I really think that the opposite could just as well hold.

see these nice polls by Gasarch

\[1\] Gasarch P vs NP poll I, 2002

\[2\] Gasarch P vs NP poll II, 2012

as for its inherent provability, there is some serious expert debate on that subject. see this ref/survey, and also a famous award-winning paper.

\[3\] is P≠NP formally independent? Aaronson

\[4\] Natural proofs Razborov/Rudich

# Answer
> 2 votes
I think that people always believe the conjecture that has "more quantifiers." We always conjecture that "there is no such number as" rather than "there is a number" or that "there are infinitely many such numbers" rather than "there are no more numbers larger than this." One reason should be that we feel that if there was such a number/bound, then we could find it/guess it.

With P=NP, if you thought that they were equal, then you should think that there is an algorithm for SAT, again a constructive thing, which if we cannot show that exits, we conjecture that it does not. At least after a lot of smart people have worked on it and could not find it.

Note that P=NP is different from number theory conjectures, which are based on some empirical evidence, like assuming that primes behave like random numbers. Here there is no supporting assumption, except that until now no one could find an algorithm. I suppose this makes the conjecture "less likely" but of course there can be no formal way of assigning probabilities to mathematical statements.

But probably you are better off reading the opinions of experts, see here: http://en.wikipedia.org/wiki/P\_versus\_NP\_problem#Reasons\_to\_believe\_P\_.E2.89.A0\_NP

---
Tags: nondeterminism, polynomial-time
---


# Question
Title: How many cookies in the cookie box? -- Tiling stars
With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit in one layer:

Almost! Is there a way they could have fit? How well can we tile stars, anyway? Given that these are regular six-pointed stars, we could certainly use the well-known hexagon tilings as an approximation, like so:

Messed up the one to the upper right, whoops.

But is this optimal? There's plenty of room between the tips.

For this consideration, let us restrict ourselves to rectangular boxes and six-pointed, regular stars, i.e. there are thirty degrees (or $\frac{\pi}{6}$) between every tips and its neighbour nooks. The stars are characterised by the inner radius $r\_i$ and outer radius $r\_o$:

\[source\]

Note that we have hexagons for $r\_i = \frac{\sqrt{3}}{2} \cdot r\_o$ and hexagrams for $r\_i = \frac{1}{\sqrt{3}} \cdot r\_o$. I think it's reasonable to consider these the extremes (for cookies) and restrict ourselves to the range in between, i.e. $\frac{r\_i}{r\_0} \in \Bigl\[\frac{1}{\sqrt{3}}, \frac{\sqrt{3}}{2}\Bigr\]$.

My cookies have $r\_i \approx 17\mathrm{mm}$ and $r\_o \approx 25\mathrm{mm}$ ignoring imperfections -- I was going for taste, not form for once!

What is an optimal tiling for stars as characterised above? If there is no static best tiling, is there an algorithm to find a good one efficiently?

# Answer
> 15 votes
Let me answer your question partially for the hexagram case.

You can make the following tiling

$\hskip1.2in$

By this you will cover 12/14=6/7 of the plane (count the triangles in the dashed quadrilateral).

Is this optimal? I would think so. Although I am not giving a proof I will provide some arguments. One can ask, how good we can fill the space (triangle) in between the pointy spikes. In the above tiling we fill half of it. Can we do better?

$\hskip20mm$

It is possible that two hexagram will intersect this space, but then they cover very little of its area (without proof). If there is only one hexagram intersecting I assume that its tip touches the concave corner of the other hexagram as depicted in the picture. If this would not be the case we can improve by moving the intersecting hexagram to this corner (again no proof here). Under these assumptions it is not hard to see that the case where there is side-to-side contact maximizes the intersection. If you do the math, then you will find out that the area of the intersection equals $$\frac{\sec ^2(x)}{2 \sqrt{3} \tan (x)+2}.$$

The plot of this function looks like this and shows that our intuition was right.

$\hskip30mm$

# Answer
> 0 votes
the following is not offered as a definitive or specific/ superior attack on this possibly unexpectedly complex problem but as additional *scientific/ theoretical* angles/ general study not covered so far.

1st this general area is known/ classified as "bin packing" and this is a 2d case. there are some famous proofs from mathematics that are related eg the 3d case of Keplers inquiry into sphere packing which was an open problem for centuries and "recently" solved with computer proof by Hales. an example 2d case that is used daily in industry is for optimizing chip layouts. obviously this is different than the problem but can point to some of the complexity of these types of problems. for example there does not seem to be any theory that requires/ indicates that a 2d case would be simpler than a 3d case. also note that a simple rectangular boundary does not necessarily help simplify the solution other than say, a polygonal boundary.

there could be an analytic solution possible if some kind of basic definition/ scheme of "regular tiling" was given in the problem statement such as placement on a grid etc. in which case calculus equations might be derivable and an optimum findable.

the conditions of the problem (maybe counterintuitively) do not seem to lead to an analytic optimal solution. this may be surprising to some but very similar problems of tiling the plane are known to be undecidable (this was a famous result years ago and there are many references and even ongoing research). a key difference between the decidable (solvable/ analytic) and undecidable problems is whether the tiling is "regular". the problem above refers to "regular stars" but does not refer to "regular tiling". the other current answer assumes a kind of regular tiling or order, but note that even defining "regular tiling" can be very tricky formally/ mathematically.

problems such as this are generally quite amenable to genetic algorithms. such an algorithm can find "very good" packings which are unlikely to be improved by much, and perhaps some bounds can be placed on their optimality via very ingenious methods (ie must be within a small error percent of optimal), but cannot prove any are optimal.

here are some refs found that are generally directly applicable:

# Answer
> 0 votes
While this particular problem probably has not been studied, such questions have been asked by Laszlo Fejes Toth and are known as packing problems. I strongly recommend the third chapter of the Pach-Agarwal book.

---
Tags: algorithms, optimization, computational-geometry, tiling
---


title: More efficient DFS on trees

text:
# Question
Title: More efficient DFS on trees
Lets say for simplicity sakes I have a simple **balanced** binary tree of **height h** and I am doing Depth First Search. I generally do the following skeletons:

```
def dfs(node root):
    //Pre actions
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

    // Post actions

```

Now when I look at this code I know its worst case asymptotic bound is O(n). But perhaps I can do better in some cases. So I want to ask a few things and see if you guys agree:

1. If the last level of the tree is very sparse. We will still make all those recursive calls when node-\>left and node-\> right is null. these will be $2^h$ checks. Would I be correct in arguing that we should place an additional check in the pre conditions check to avoid at least some of those $2^h$ extra calls?

\`

```
if not node.left and not node.right:
    return

```

or go even further and add an additional check:

```
 if not node.right.left and not node.right.left:
     // Do some book keeping
     return
 if not node.left.left and not node.left.right:
     // Do some book keeping
     return

```

IOW is it legit to argue that in cases where the last level is mostly empty, calling dfs recursively is less(much less in certain languages?) performant vs doing the above additional checks at that last level and though we will still be worst case O(n) time bound(we visit everything), we can be better in such cases?

2. Do compiler optimizations render my point (1) moot in certain cases. What are those cases?

# Answer
While this indeed saves recursive calls, DFS is often described by recursion for convenience of writing/implementing.

Notice that you can actually unroll the entire recursion tree and implement iterative DFS.
> 4 votes

# Answer
If you want to cover the entire tree then your algorithm must run in $\Omega(n)$, assuming $n$ is the number of nodes in the tree. You are right, however, that you could optimize the code by checking that the child is non-empty before calling the function. This is an optimization that the compiler probably wouldn't do on its own. This optimization could improve your algorithm, but its running time will still be asymptotically $O(n)$ (assuming $O(1)$ processing per node); at most you improve the constant.
> 4 votes

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: what is the best way to approach the construction of nondeterministic PDA's?
I'm trying to construct a PDA for $L = \\{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then nondeterministically guess "$01$" in $w$, however I am stuck with the rest. I understand the condition $i/3=j/2$, but how do I make my PDA accept that? Does it have to be nondeterministic too? How do I approach this?

# Answer
For the "$w$ part", as you said (or implied) yourself, you don't need the stack at all. After switching to the "$0^i1^j$ part", in some state $s\_2$, you can put for the $0$'s in the input alternatingly first an $a$ on the stack, then delete it with a $b$ for the second $0$, then add a $c$ for the third $0$, then start over. By adding only two of the three symbols for each stream of three zeros (as you delete $a$), you get $2/3i$ symbols in the stack which is just equal to $j$. You get a stack like this: $kbcbc\ldots$ ($k$ being the bottom stack symbol).

Now, you just have to delete each $b$ or $c$ with the ones coming on the input tape and accept iff you reach the bottom of the stack ($k$) when the input is complete.

The second part of the PDA might look something like this ($\lambda$ being the empty word):

$(s\_2, 0, k) \rightarrow (s\_2, ak)$

$(s\_2, 0, a) \rightarrow (s\_2, b)$

$(s\_2, 0, b) \rightarrow (s\_2, cb)$

$(s\_2, 0, c) \rightarrow (s\_2, ac)$

$(s\_2, 1, c) \rightarrow (s\_3, \lambda)$

$(s\_3, 1, c) \rightarrow (s\_3, \lambda)$

$(s\_3, 1, b) \rightarrow (s\_3, \lambda)$

$(s\_3, \lambda, k) \rightarrow (s\_e, k)$
> 1 votes

# Answer
I have thought about this about realized that the solution is the following:

1) read w how i described 2) as you read 0, put 000 on the stack, and then as you read 1, remove 00 from the stack, and that's how you get the correct PDA.

So, the PDA is the following(z0 is the bottom marker):

(q0, 0, z0, (q0, z0))

(q0, 1, z0, (q0, z0))

(q0, 0, z0, (q1, z0)) // non-deterministically guess that the next 2 symbols are "01"

(q1, 1, z0, (q2, z0)) // accept "01"

(q2, 0, z0, (q2, 000z0)) // put 000 when we see the bottom marker

(q2, 0, 0, (q2, 0000)) // put 000 on top of the other zeros

(q2, 1, 000, (q2, 0)) // remove 00, here I omitted the extra state responsible for deleting 3 symbols at once and wrote it as "the PDA is seeing "000""

(q3, lamda, (q3, z0)) // stop

Really sucks that I always overlook the little parts in formal definitions of things, I didn't know that the string that I could put on the stack could be of any length and not just 1 symbol.
> 0 votes

---
Tags: formal-languages, context-free, pushdown-automata
---


# Question
Title: Multiprocessor Scheduling is NP-Complete
Consider this version of MS where we have set $A$ of tasks, $l(a)$, length of each task in $A$ and $m$ number of processors and also a deadline $D$. The question is where we can partition A into m disjoint subsets, $A = A\_1 \cup A\_2 \cup \ldots \cup A\_m$ such that we have: $$ max \left\\{ \sum \_{a \in A\_i} l(a): 1 \le i \le m \right\\} \le D ? $$

My attempt(Also hint from Garey & Johnson) consider $m = 2$ and $D = \frac{1}{2} \sum \_{a \in A} l(a)$. if so we have $$ max \left\\{ \sum \_{a \in A\_1} l(a), \sum \_{a \in A\_2} l(a) \right\\} \le \frac{1}{2} \sum \_{a \in A} l(a) ? $$

this implies that we should have $\sum \_{a \in A\_1} l(a) = \frac{1}{2} \sum \_{a \in A} l(a)$ and also $\sum \_{a \in A\_1} l(a) = \frac{1}{2} \sum \_{a \in A} l(a)$\**(if we have such a partition!)\**, otherwise we will have a contradiction because if for example $max$ was $\sum \_{a \in A\_1} l(a)$ we had $$ \sum \_{a \in A\_1} l(a)\< \frac{1}{2} \sum \_{a \in A} l(a) \\ \sum \_{a \in A\_2} l(a)\< \frac{1}{2} \sum \_{a \in A} l(a) $$ and if we sum the last two inequalities we get this contradiction: $$ \sum \_{a \in A} l(a) \< \sum \_{a \in A} l(a) $$

so now we know that they are equal, and we see that our problem is now an instance of partition(or subset sum with sum equal $B/2$ where $B$ is sum of all elements of A) and we know that partition is $NPC$ so our main problem is $NPC$ too by restriction.

Is my argument correct??

# Answer
The deadline is maximum time a single processor can take to complete its tasks (the subset allocated to that processor) where as you are considering deadline as the total of each processor's time.

Let's say there are 6 tasks each with 1 unit of time. Then your example of taking deadline by half of total time of all tasks become 6/2 = 3. Now comes the number of processors which you take to be 2. The task now is to divide the 6 tasks into 2 groups such that the **total time of each of the 2 groups is less than or equal to deadline**. You cannot compare the sum of total time of each group time with the deadline as the deadline is about the maximum time a **single group** can take.

In terms of showing that the problem is NP-Complete, I guess you will have to show a reduction of your problem to any of the known NP-Complete problems. Intuitively, I think that this problem can be reduced to a form of subset sum problem which is NP-Complete.
> 1 votes

---
Tags: np-complete, partition-problem, check-my-answer
---


# Question
Title: Are there programs that never halt and have no non-termination proof?
Like black holes in computer science. We can only know they exist but when we have one of them we will never know it's one of them.

# Answer
> 23 votes
There are indeed programs like this. To prove this, let's suppose to the contrary that for every machine that doesn't halt, there is a proof it doesn't halt.

These proofs are strings of finite length, so we can enumerate all proofs of length less than $s$ for some integer $s$.

We can then use this to solve the halting problem as follows: Given a Turing Machine $M$ and an input $x$, we use the following algorithm:

```
s := 0
while (True)
    test if machine M halts on input x in s steps
    look at all proofs of length s and see if they prove M doesn't halt on input x
    set s := s + 1

```

If $M$ halts on input $x$, then it halts in some finite number of steps $s$, so our algorithm terminates.

If $M$ doesn't halt on input $x$, then by our assumption, there's some proof length $s$ where there's a proof that $M$ doesn't halt. So in this case, our algorithm always terminates.

Thus, we have an algorithm deciding the Halting problem which always terminates. But we know this cannot exist, so our assumption that there's always a proof of non-halting must be false.

# Answer
> 7 votes
For a somewhat more concrete example, let us assume that the theory we are using for our proofs has the following (quite reasonable, IMO) features:

1. It is is consistent; that is, it cannot prove a contradiction.
2. Its set of axioms is recursively enumerable.
3. Its proofs can be written down as finite bitstrings.
4. The question of whether a given string encodes a well-formed and correct proof in it is algorithmically decidable in finite time.
5. It is expressive enough to admit a proof of Gödel's second incompleteness theorem, which says that it cannot prove its own consistency.

With those assumptions, the following program will never halt, but cannot be proved (within the scope of the theory we are using) not to halt:

```
let k := 0;
repeat:
    let k := k + 1;
    let s := binary expansion of k, excluding leading 1 bit;
while s does not encode a proof of a contradiction;
halt.

```

The key detail here is the first assumption above, namely that the theory we are using for our proofs is consistent. Obviously, we need to assume this, for our proofs to be worth anything, but Gödel's second incompleteness theorem says that, for any reasonably expressive and effectively axiomatized theory, we cannot actually prove this (except possibly in some *other* theory, whose consistency we then need to assume, etc. etc.).

---
Tags: halting-problem, correctness-proof
---