# Question
Title: Number Partitioning targeting a Ratio of subset sums?
I have a problem, which appears to be similar to number partitioning: a set of numbers partitioned (two-way), such that the sum of the numbers in each subset are as close as possible to a targeted ratio (instead of having the minimum difference, as in the number partitioning problem). Can I use the same algorithms? How would I modify them? Is another approach more suitable?

Context:

I am implementing a load-balancing algorithm, for a ***work conserving*** Group Weighted Round Robin (GWRR) scheduler. In some corner-case (some groups have less tasks than CPUs in the system), I want to partition the weighted groups and assign them to the subsets of a partitioning of the set of CPUs, so that the ratio of the sums of (predicted) CPU idle times, in the subsets of the CPU partition, is as close as possible to the ratio of the weight sums, in the subsets of the group partition. The group partition splits the groups, using a normal number partitioning algorithm (CKK), so that group weight sums, in each subset, have the minimum possible difference (but they are unlikely to match, in the general case).

Any ideas?

# Answer
> 1 votes
Yes. Suppose the numbers are $x\_1,\dots,x\_n$ and the target ratio is $r$. Define

$$y=\left\lfloor {1-r \over 1+r} \times (x\_1 + \dots + x\_n) \right\rceil,$$

and then look for the partition of $x\_1,\dots,x\_n,y$ that has minimum difference. I suspect this might be either the solution to your original problem, or very close to it.

Why? A partition of $x\_1,\dots,x\_n$ with exactly the ratio $r$ will have one group whose total is $c (x\_1+ \dots + x\_n)$ and another whose total is $cr(x\_1+\dots+x\_n)$. These two must sum to $x\_1+\dots+x\_n$, so we find that $c+cr=1$, i.e., $c=1/(1+r)$, so their difference is

$$c(x\_1+\dots+x\_n) - cr(x\_1+\dots+x\_n) = {1-r \over 1+r} (x\_1+\dots+x\_n).$$

We have defined $y$ to be this difference, rounded to the nearest integer. So, if you add $y$ to the smaller group, you get a perfect partition of $x\_1,\dots,x\_n,y$ with difference zero. And the converse is true as well.

---
Tags: process-scheduling
---


# Question
Title: Reducing max flow to bipartite matching?
There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item to be matched, then add appropriate edges.

There's certainly a way to reduce maximum flow to maximum bipartite matching in polynomial time, since both of them can be each individually be solved in polynomial time. However, is there a "nice" polynomial-time reduction from max-flow (in general graphs) to maximum bipartite matching?

# Answer
Strangely enough, no such reduction is known. However, in a recent paper, Madry (FOCS 2013), showed how to reduce maximum flow in unit-capacity graphs to (logarithmically many instances of) maximum $b$-matching in bipartite graphs.

In case you are unfamiliar with the maximum $b$-matching problem, this is a generalization of the matching, defined as follows: the input is a graph (in our case, a bipartite graph), $G=(V,E)$, and a set of integral demands for each vertex, with the demand of vertex $v$ denoted by $b\_v$. The goal is to find a largest possible set of edges $S$ such that no vertex $v$ has more than $b\_v$ edges in $S$ incident on $v$. It is a simple exercise to generalize the reduction from bipartite matching to maximum flows and show a similar reduction from bipartite $b$-matching to maximum flows. (One of) the surprising result(s) of Madry's paper is that in some sense these problems are equivalent, giving a simple reduction which reduces maximum flow in unit-capacity graphs (generally, graphs where the sum of capacities, $|u|\_1$ is linear in the number of edges, $m$) to a $b$-matching problem in a graph with $O(m)$ nodes, vertices and sum of demands.

If you're interested in details, see section 3, up to Theorem 3.1 and section 4 (and proof of correctness in Appendix C) of the ArXiv version of Madry's paper, here. If the terminology is not self-evident, see section 2.5 for a recap concerning the $b$-matching problem, and bear in mind that $u\_e$ is the capacity of edge $e$ in the original max flow instance.
> 7 votes

# Answer
So here is a try at answering your question:

Konig’s theorem on bipartite matchings proved and consequently reduced using the Max-Flow Min-Cut theorem. Konig’s theorem states the following. If G a bipartite graph, then max{|M| : M is a matching } = min{|C| : C is a cover}. Proof. The part max{|M|} ≤ {|C|} is trivial. Let P and Q be the bipartition classes of G. We add two vertices, r and s to G, and arcs rp for every $p\in P$ and qs for every $q \in Q$, and direct edge pq from $p\in P$ to $q\in Q$. This is a digraph $G\_{∗}$. We define capacities u(rp) = 1, u(pq) = $\infty$, u(qs) = 1. Let x be a feasible integral flow x, then x(e) = 0 or 1, so we can define M = {$e \in E$ : x(e) = 1}. M is a matching with |M| = $f\_{x}$. Next, a matching M in G gives rise to a feasible integral flow x in $G\_{∗}$ with flow value $f\_{x}$ = |M| as follows. Define x(pq) = 1 if $pq \in M$, x(rp) = 1 if p is incident to an edge in M, x(qs) = 1 if q is incident to an edge in M, in all other cases x(e) = 0. Thus a maximum size matching M in G corresponds to a maximum flow in $G\_{∗}$, whose size equals that of a minimum cut by the Max-Flow Min-Cut theorem. Consider a minimum r − s cut δ(R). It has finite capacity, so it contains no arc pq. Then every edge of G is incident with an element of C = (P\R) $\cup (Q \cap R)$, that is, C is a cover. Moreover, u(C) = |P \R|+$|Q \cap R|$ and so C is a cover of size |M|.

I mean this is everything in my opinion that you asked in the question and this is my potential answer :).
> -2 votes

---
Tags: reductions, network-flow, bipartite-matching
---


# Question
Title: When should you use the existential and universal quantifiers for Relational Calculus?
Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus?

**Given this schema:**

```
Hotel(hotelNo, hotelName, city)

```

The expression below gets all hotel names based in London (expressed in Domain Relational Calculus)

$$\mathrm{HotelName|(\exists hNo,cty)(Hotel(hNo,hotelName,cty)\wedge cty=\\,\\,"\\!\\!London\\!")}$$

Why does the existential quantifier required for this example? Wouldn't this be the equivalent `{hotelName | (Hotel(hNo, hotelName, cty) AND cty='London')}`

And why is only `hNo`and `cty` selected for the existential quantifier? What about the `hotelName`?

**Source:** Herts University - Advanced Database Course

# Answer
This question is related to the very basics of database theory, finite model theory and logics. I would strongly suggest Abiteboul's book on *Foundations of Databases*, or Libkin's book on *Finite Model Theory*.

Very roughly stated, a database is a collection of facts, and a query is a logical formula, which is used to specify certain patterns to be matched against the database. The most common database query language is *unions of conjunctive queries*, which is simply a disjunction of *conjunctive queries*. These are existentially quantified queries and there is NO universal quantification at all. The query in the question is indeed the simple conjunctive query

$\exists \ x \ {Hotel(x, y, london)} $

where $x$ and $y$ are logical variables and $london$ is a constant. Intuitively, the $x$ variables are to be matched to hotel numbers, and $y$ variables to hotel names. Now, in this formula, $y$ is a *free variable*, i.e. it is not bound to any quantifier. It is wrong to assume that it is bound to a universal quantifier. Such variables are also called the answer variables as these are the variables for which you want to retrieve answers. Note that $x$ is not an answer variable; so, you are not interested in the hotel numbers. All you want to say with this query is: Give me all the names of the hotels in London! Differently, consider this query

${Hotel(x, y, london)} $

where $x$ is also a free variable. It asks for all names + numbers of the hotels in London. A Boolean query is a special case of a conjunctive query that does not contain any free variables. For instance, the query

$\exists \ x,y \ {Hotel(x, y, london)} $

has no free variables and asks a yes/no question: Is there a hotel in London (with some hotel number and name)? Overall, please have a look at the reference books, and simply learn the query semantics.
> 4 votes

# Answer
You cannot have free variables in your expression, i.e. all variables must either be quantified, or appear in the return tuple. So the answer is - always, unless the variable appears in the output tuple
> 2 votes

# Answer
A query in relational calculus is basically a set constructor. What appears on the right side of the "|" ("such that") symbol is a first-order predicate logic sentence, on which all variables should be quantified (otherwise the sentence is meaningless), with the exception of the ones that appear before the "|" symbol. They become the ones that function as arguments for the set constructor.

Could the language use some form of inference or implicit quantification? In principle, yes, but in practice this would create more confusion. When writing any kind of code, we should always err on the side of precision and rigour. Language implementation should not protect us from the burden of clarity.
> 1 votes

# Answer
I was wondering much the same. After acquiring the Ramakrishnan text (2nd edition) I found the answer on page 109:

> Let each free variable in a formula $F$ be bound to a tuple value. For the given assignment of tuples to variables, with respect to the given database instance, $F$ evaluates to (or simply 'is') $\text{true}$ if one of the following holds:
>
> * ...
> * $F$ is of the form $\exists R(p(R))$, and there is some assignment of tuples to the free variables in $p(R)$, including the variable $R$, that makes the formula $p(R)$ true.
> * $F$ is of the form $\forall R(p(R))$, and there is some assignment of tuples to the free variables in $p(R)$ that makes the formula $p(R)$ true no matter what tuple is assigned to $R$.

It appears that what we are essentially doing in the form $\\{ T | p(T) \\}$ is finding the truth set of the expression $p(T)$ where $T$ ranges over all tuples in the relation under the expression.

Given a relation instance $R$ and some arbitrary expression $p(R)$ we can return the entire tuple $\\{ r | r \in R \land p(r) \\}$. Alternately we can *project* and return only those fields we need, by introducing a new tuple variable e.g. $s$. Doing this requires that we have a means to specify the field names to be extracted:

$$\\{ s | r \in R \land p(r) \land s.attr1 = r.attr1 \land ... \land s.attr\text{n} = r.attr\text{n} \\}$$

Ramakrishnan describes this exactly. Given the query:

$$\\{ P | ∃S ∈ Sailors ( S.rating = 7 ∧ P.name = S.name ∧ P.age = S.age ) \\}$$

the following is written:

> This query illustrates a useful convention: $P$ is considered to be a tuple variable with exactly two fields, which are called name and age, because these are the only fields of $P$ that are mentioned and $P$ does not range over any of the relations in the query; that is, there is no subformula of the form $P \in Relname$.

At the end of the section on TRC the point is made that we can choose to return an *entire tuple* containing all the fields, or a tuple containing only a subset of the fields. If we want the subset (the projection) we have to introduce the new variable.

In this case the equality comparisons are the notation used to specify the fields that will be in $P$.

Hope that helps.
> 1 votes

---
Tags: database-theory, databases, relational-algebra
---


# Question
Title: Using Big $O,\Omega,\Theta$, how would you represent these equations?
How would you write the following equations in $O,\Omega,\Theta$ notation? $$ \begin{align\*} t(n) &= 4n^4 + 3n^5 + 3n^6 \\ g(n) &= 2n^6 + 5\log n \\ f(n) &= 50n^5 \end{align\*} $$

# Answer
Let's visit the basic definition of the asymptotic notations you have written. In computer science, these notations are mostly used to study the growth of the runtime of an algorithm with the input size.

In Big-O notation, we write $$f(x) = O(g(x))$$ if and only if there exists a positive real number M and a real number $x\_0$ such that $$|f(x)| \leq M |g(x)| \text{ } \forall x \geq x\_0 $$

Similarly, we have

$f(n)= \Theta (g(n)) \text{ iff } k\_{1}\cdot g(n)\leq f(n)\leq k\_{2}\cdot g(n) \text{ for some positive } k1, k2$ and
$f(n)=\Omega (g(n)) \text{ iff } f(n)\geq k\cdot g(n) \text{ for some positive } k$

Now having the definitions in hand, your questions can be answered quickly.

$t(n) = 4n^4+3n^5+3n^6 \leq 10n^6 \text{ ( since } n^4 \leq n^6 \text{ and } n^5 \leq n^6 \text{ ) }$ $ = O(n^6) \text{ from the defintion } $

Also, $ t(n) \geq 3n^6 =\> 3n^6 \leq t(n) \leq 10n^6 =\> t(n) = \theta(n^6) $

and, $ t(n) \geq 3n^6 =\> t(n) = \Omega(n^6) $

Now you can use the same logic for the other two to get,

$ g(n) = O(n^6) = \theta(n^6) = \Omega(n^6) $
$ f(n) = O(n^5) = \theta(n^5) = \Omega(n^5) $

Note: If you look closely at the definitions of the $ O, \theta, \Omega$ notations, you will see that there can be many possible answers for your questions. For example,

$ f(n) = 50n^5 \geq n^4 \geq n^3 \geq n^2 \geq log n .. $
$ =\> f(n) = \Omega(n^4) = \Omega(n^3) = \Omega(n^2) = \Omega(log n) $

If you are really interested in complexity analysis and asymptotics, have a look at https://en.wikipedia.org/wiki/Big\_O\_notation#Equals\_sign. It discusses the nuances of the notation and the notational abuse in using equality in my answer for simplicity.
> 4 votes

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


# Question
Title: Notation for a Kleene fixed point with a starting element
Assume a CPO $Q,\leq$ and a Scott-continuous function $f : Q \rightarrow Q$. As it is known, the chain $\bot \leq f(\bot) \leq \ldots \leq f^n(\bot)$ (where $f^n$ denotes the function $n-1$-times composed with itself) leads to a fixed point of $f$.

It is also clear, if $f$ is inflationary, that for any $q \in Q$, the chain $q \leq f(q) \leq \ldots \leq f^m(q)$ leads to a fixed point. (This follows immediately by just considering the subset $\\{\\,p\\,|\\, p \in Q \wedge q \leq p\\}$, which is also a CPO.)

This second form is often more useful in practice. But how to denote it? While the fixed point of $f$ is easily written $\text{fix} f$, is there a standard convention for the second form? Writing $\text{fix} f(q)$ seems intuitive but is - strictly speaking - wrong, since $f(q)$ is not a function (it might also be confusing in the case of higher-order functions).

edit: Added note, that $f$ must be inflationary.

# Answer
Suppose $Q$ is a join semilattice. Define $g:Q \to Q$ by

$$g(x) = f(x) \sqcup q.$$

Then $\text{fix} \\; g$ is equal to the least fixpoint of $q,f(q),f^2(q),\dots$. So, at least for cpo's that form a join semilattice, you can indicate it pretty naturally using existing notation -- there's not a strong need to invent a new notation (though you could of course introduce one if you wanted).

If $Q$ is not a join semilattice, I think you can still define

$$g(x) = \sup \\{ f(x), q \\}$$

and then do the same thing. The least fixpoint of $q,f(q),f^2(q),\dots$ will be $\text{fix} \\; g$.
> 2 votes

# Answer
Note that, in general, there might not be such a fixed point.

E.g. $$ \begin{array}{l} f : \mathbb{N}\_\bot \to \mathbb{N}\_\bot\\ f(\bot) = \bot\\ f(\lfloor n\rfloor) = \lfloor n + 1\rfloor \end{array} $$ is the standard denotation of the lazy lambda calculus function $\lambda n.\ n+1$. It is Scott-continuous.

Its least fixed point is $\bot$ -- actually, there are no other fixed points. So, if we consider the "chain" starting from $q = \lfloor 42 \rfloor$, which is $\lfloor 42 \rfloor, f(\lfloor 42 \rfloor), f^2(\lfloor 42 \rfloor), \ldots$ we discover that it's not even a chain, and as a set has no supremum in $\mathbb{N}\_\bot$.

Hence, one should be careful here:

> It is also clear, that for any $q \in Q$, the chain $q \leq f(q) \leq \ldots \leq f^m(q)$ leads to a fixed point. (This follows immediately by just considering the subset $\\{\\,p\\,|\\, p \in Q \wedge q \leq p\\}$, which is also a CPO.)

If that is a chain, then it leads to a fixed point -- but it might not be a chain. Also, the subset you mention is a CPO: in the previous example it is the singleton CPO $\\{q\\}=\\{\lfloor 42 \rfloor\\}$. However, in general, $f$ is not an internal operation on that CPO. Indeed, in the example we immediately escape that.
> 1 votes

---
Tags: notation, fixed-point
---


# Question
Title: m-CNF formulas satisfiability approximation
I am reviewing for a test, and i am stuck on this question.

the problem is to show it is hard to approximate (for any constant) the following problem:

given m CNF formulas f1,..,fm over variables x1,..,xn find the assignment which maximizes the number of satisfied formulas.

I believe I need to reduce this problem to some kind of graph problem (CSG,IS,CLIQUE), which I know cannot be approximated for any constant. I can't find a way to do this. To what problem do I reduce this to?

thank you.

# Answer
If such a constant-factor approximation algorithm would exist, and it would run in polynomial-time, you could use it to solve CNF-SAT in polynomial time. Since CNF-SAT is NP-hard, this may give you the desired result.

Sketch: Given a CNF-formula f, feed sufficiently many copies of the formula to your approximation algorithm. If f is not satisfiable, the algorithm must always output 0. If f is satisfiable, it should output a number \> 0 (at least, if the other numbers are chosen correctly).
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Bounded Integer Edge Weights, Dijkstra's Algorithm
I'm trying to understand how we can get the time complexity of Dijkstra's Algorithm down from O(V²) (for a matrix-implemented Dijkstra's) to O(V) if the edge weights of our graph are bounded by a constant C. I've read up on this MIT lecture but can't really wrap my head around the explanation.

It says that all paths are less than (|V|-1) * C, but why can't they be equal to (|V|-1) * C? For example, if the graph has one edge between each node and the weight on every node is C. Shouldnt it be less than or equal to?

# Answer
> 0 votes
In the case of your example, the shortest path is of length C since all paths are 1 edge long; there is an edge between each pair of node.

The figure of (|V|-1)C comes from the situation where all your nodes form a single chain, with edge weights of C. Then, the path between the first and last node on the chain is of length (|V|-1)C.

---
Tags: graphs, graph-traversal, weighted-graphs
---


title: Program Correctness, The specification

text:
# Question
Title: Program Correctness, The specification
From Wikipedia: In theoretical computer science, correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification.

But the problem is that to get the "appropriate" specification is not a trivial task, and there is no 100% correct method (as far as i know) to get the right one, it just an estimation, so if we are going to take a predicate as a specification just because it "looks" like the "one", why not taking the program as correct just because it "looks" correct?

# Answer
> 30 votes
First off, you're absolutely right: you're on to a real concern. Formal verification transfers the problem of confidence in program correctness to the problem of confidence in specification correctness, so it is not a silver bullet.

There are several reasons why this process can still be useful, though.

1. Specifications are often simpler than the code itself. For instance, consider the problem of sorting an array of integers. There are fairly sophisticated sorting algorithms that do clever things to improve performance. But the specification is fairly simple to state: the output must be in increasing order, and must be a permutation of the input. Thus, it is arguably easier to gain confidence in the correctness of the specification than in the correctness of the code itself.
2. There is no single point of failure. Suppose you have one person write down a specification, and another person write the source code, and then formally verify that the code meets the spec. Then any undetected flaw would have to be present in *both* the spec *and* the code. In some cases, for some types of flaws, this feels less likely: it's less likely that you'd overlook the flaw when inspecting the spec *and* overlook the flaw when inspecting the source code. Not all, but some.
3. Partial specs can be vastly simpler than the code. For instance, consider the requirement that the program is free of buffer overrun vulnerabilities. Or, the requirement that there are no array index out-of-bounds errors. This is a simple spec that is fairly obviously a good and useful thing to be able to prove. Now you can try to use formal methods to prove that the entire program meets this spec. That might be a fairly involved task, but if you are successful, you gain increased confidence in the program.
4. Specs might change less frequently than code. Without formal methods, each time we update the source code, we have to manually check that the update won't introduce any bugs or flaws. Formal methods can potentially reduce this burden: suppose the spec doesn't change, so that software updates involve only changes to the code and not changes to the spec. Then for each update, you are relieved of the burden to check whether the spec is still correct (it hasn't changed, so there's no risk new bugs have been introduced in the spec) and of the burden to check whether the code is still correct (the program verifier checks that for you). You still need to check that the original spec is correct, but then you don't need to keep checking it each time a developer commits a new patch/update/change. This can potentially reduce the burden of checking correctness as code is maintained and evolves.

Finally, remember that specs typically are declarative and can't necessarily be executed nor compiled directly to code. For instance, consider sorting again: the spec says that the output is increasing and is a permutation of the input, but there is no obvious way to "execute" this spec directly and no obvious way for a compiler to automatically compile it to code. So just taking the spec as correct and executing it often isn't an option.

Nonetheless, the bottom line remains the same: formal methods are not a panacea. They simply transfer the (very hard) problem of confidence in code correctness to the (merely hard) problem of confidence in spec correctness. Bugs in the spec are a real risk, they are common, and they can't be overlooked. Indeed, the formal methods community sometimes separates the problem into two pieces: *verification* is about ensuring the code meets the spec; *validation* is about ensuring the spec is correct (meets our needs).

You might also enjoy Formal program verification in practice and Why aren't we researching more towards compile time guarantees? for more perspectives with some bearing on this.

# Answer
> 19 votes
D.W.'s answer is great, but I'd like to expand on one point. A specification is not just a reference against which the code is verified. One of the reasons to have a formal specification is to validate it by proving some fundamental properties. Of course, the specification cannot be completely validated — the validation would be as complex as the specification itself, so it would be an endless process. But validation allows us to get a stronger guarantee on some critical properties.

For example, suppose you're designing a car autopilot. This is a pretty complex thing involving a lot of parameters. Correctness properties of the autopilot include things like “the car will not crash against a wall” and “the car will drive where it's told to go”. A property like “the car will not crash against a wall” is really really important, so we'd like to prove that. Since the system operates in the physical world, you'll need to add some physical constraints; the actual property of the computational system will be something like “under these assumptions regarding materials science, and these assumptions regarding the perception of obstacles by the car's sensors, the car will not crash against a wall”. But even so, the result is a relatively simple property that is clearly desirable.

Could you prove this property from the code? Ultimately, that's what's going on, if you're following a fully formal approach¹. But the code has a lot of different parts; the brakes, the cameras, the engine, etc. are all controlled autonomously. A correctness property of the brakes would be something like “if the ‘apply brakes’ signal is on then the brakes are applied”. A correctness property of the engine would be “if the clutch signal is off then the engine isn't driving the wheels”. It takes a very high-level view to put them all together. A specification creates an intermediate layers where the different components of the system can be articulated together.

In fact, such a complex system as a car autopilot would have several levels of specifications with varying amounts of refinements. A refinement approach is often used in the design: start with some high-level properties like “the car will not crash against a wall”, then figure out that this requires sensors and brakes and work out some basic requirements for the sensors, the brakes and the pilot software, then refine again those basic requirements into a design of the component (for the sensor, I'm going to need a radar, a DSP, an image processing library, …), etc. In a formal development process, each level of specification is proven to meet the requirements set by the level above it, all the way from the highest-level properties down to the code.

It's impossible to be sure that the specification is correct. For example, if you got the physics wrong, the brakes might not be effective even though the math relating the brake code to the formal requirements is correct. It's no good to prove that the breaks are effective with 500kg of load if you actually have 5000kg. But it's easier to see that 500kg is wrong than to see inside the brakes code that they won't be good enough for the physical parameters of the car.

¹ <sub> The opposite of a fully formal approach is “I guess this works, but I can't be sure”. When you're betting your life on it, that doesn't seem so great. </sub>

---
Tags: formal-methods, software-verification, program-correctness
---


# Question
Title: How to find unambiguous grammar for palindromes
I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc.

```
S -> a S a
   | b S b
   | a
   | b
   | ε

```

Is there a way to convert this to an unambiguous grammar? Or is there another solution?

# Answer
First, I believe you are looking for a different word than 'unambiguous'. A grammar is ambiguous if some string in its language has two or more derivations; I'm sure that a palindromic string must have only one derivation in this grammar.

I suspect the word you really mean is 'deterministic'. YACC must declare that this grammar has 'shift-reduce' conflicts - e.g if the next letter is 'a' one cannot decide if the first, third, or fourth rule is to be applied. This is an inherent problem with palindromic languages; the core problem is that there is no way to know, during a left-to-right scan of the input string, exactly where the midpoint of the string is.

If you are permitted to change the language, you could add a new letter 'c' and use it to always (and ONLY) mark the center of each string.
> 8 votes

---
Tags: context-free, formal-grammars, compilers, parsers, ambiguity
---


# Question
Title: How could I prove that $B$ reduces to $A$ in polynomial time in this case?
Let $A$ be a decision problem with at least one yes instance and at least one no instance. Also let $B \in \textbf{P}$. How could I prove that B reduces to A in polynomial time?

Thanks in advance.

# Answer
> 2 votes
Take $a\in A$ and $b \notin A$.

the reduction defined as follows: $$f(x)=\begin{cases} a & x\in B\\ b & x\notin B \end{cases}$$

It is easy to see that $f \in \text{POLY}$ since $B\in\text{P}$, and the correctness is trivial.

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


# Question
Title: Can a regular language enforce a length limit AND disallow consecutive characters?
I was reading the venerable "How to Find or Validate an Email Address \[using Regex\]", and I came across the following statement at the bottom of the page:

> \[A\] true regular language cannot enforce a length limit and disallow consecutive hyphens at the same time.

This seems wrong to me.

I feel like if the length of a string is bounded ahead of time, you should be able to write a DFA which processes pretty much any rule on the input string, as you can just create $n$ states from the most recent states, where $n$ is the number of letters in the alphabet, repeating for the maximal length of the input string?

If this reasoning is wrong, can someone point me in the right direction?

# Answer
You are not wrong. In fact, *any* finite language $L$ over a finite alphabet $\Sigma$ is regular. If $L$ is finite, there must be an integer $d$ such that for all $x \in L$ it holds that $|x| \le d$. Let $|\Sigma| = s$ and construct a complete $s$-ary tree of depth $d$, where each edge from a node to one of its children is a transition associated to some $c \in \Sigma$.

We can see that such a tree enumerates all the strings over $\Sigma$ of length at most $d$; this means that each string of $L$ must correspond to some node of the tree. Marking as an accepting state every such node yields a DFA for $L$.

Notice that the resulting DFA may be very ugly, but it's a valid DFA nonetheless, and that is sufficient if we are only concerned with regularity.
> 3 votes

# Answer
Yeah, that claim looks bogus to me. Regular languages are closed under intersection. The set of all words of length at most $k$ is regular; the set of all words with no consecutive hyphens is regular; so their intersection is regular. Every regular language can be matched by a regular expression.

That said, the resulting regular expression might be awfully ugly... Also, it's not clear whether it is all that important to reject email addresses with a domain name that is longer than 63 characters in any case.
> 0 votes

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


# Question
Title: Number of "hamiltonian tours" from upper left to lower left corner of a grid graph?
I got the following as an interview question:

Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction. This is the number of Hamiltonian paths from upper left to lower left: a path such that every vertex is visited only once, and (this follows from the first statement) such that each edge is used at most once.

The grid world is a 4x10 matrix (4 rows and 10 columns).

Is it really this hard?

Matrix method for counting Hamiltonian cycles

And:

Number of Hamiltonian Paths from Lower Left to Upper Right

---

These papers seem dated--94, 97--but are they really asking a question that qualifies for publishing in a combinatorical journal?

---

Then I ran into this: SO question: number of Hamiltonian paths

And am thinking dynamic programming, or divide and conquer...but it is really not clear how one would go about doing this. Is there a way to solve this problem in reasonable time?

---

# Answer
I think a divide and conquer strategy is going to work here. The asymptotic runtime isn't great, but fortunately our graph is of fixed size. Pick some arbitrary node, $v$, and partition the rest of the nodes into two sets. The number of hamiltonian tours is the number of paths that start at the upper left, go through all nodes in the first side of the partition and end at $v$ multiplied by the number of paths that start at $v$, go through every node in the second half and end at the bottom left corner summed over every possible such partition. Recursively do this for each partition.
> -1 votes

---
Tags: dynamic-programming, discrete-mathematics, divide-and-conquer, hamiltonian-path
---


# Question
Title: Examples of Context-sensitive grammars which produces non-indexed language
Well known example of Context-sensitive grammar which produces language $\\{a^nb^nc^n|n\geq 1\\}$ is widely used in various papers. But actually, while this language is definitely context-sensitive, it is also belongs to smaller subset of CS-languages: it is indexed language, because it can be described with indexed grammar as well.

What I'm looking for, it is example of Context-sensitive grammar which produces non-indexed language. From this paper it is known that language $\\{(ab^n)^n|n\geq 1\\}$ is not indexed. But there is no described grammar for this language.

So could somebody describe CS-grammar for given non-indexed language example, or provide with any other example?

# Answer
> 2 votes
If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)

---

Example of building word $abbbabbbabbb$ ($n=3$) (added by @Andremoniy):

1) $S\Rightarrow DTA\Rightarrow DDTaA\Rightarrow DDDaaA$ - "inflate" string $n$ times;

2) $\Rightarrow DDabDaA\Rightarrow DabDbDaA\Rightarrow abDbDbDaA\Rightarrow abbDDbDaA\Rightarrow abbbDDDaA\Rightarrow \dots$ - we built 1st subword $abbb$, move on

3) $\Rightarrow abbbDDabDA\Rightarrow abbbDabDbDA\Rightarrow abbbabDbDbDA\Rightarrow abbbabbbDDDA\Rightarrow\dots$ - two subwords $abbbabbb$ are built, move on

4) $\Rightarrow abbbabbbDDAb\Rightarrow abbbabbbDAbb\Rightarrow abbbabbbAbbb\Rightarrow abbbabbbabbb$

# Answer
> 2 votes
First of all I'm very appreciated to @HendrikJan for his example of noncontracting grammar (and his answer which I formally accept). Just to completely end this issue, as I was looking for "canonical" CS grammar ($\alpha A\beta\rightarrow\alpha\gamma\beta$), I'm publishing here my version of transformed @HendrikJan's example to full CS grammar:

$S\rightarrow DTX|ab\\ S\rightarrow DTA|DA$

expanded $DA\rightarrow ABD$:

$DA\rightarrow DY\\ DY\rightarrow WY\\ WY\rightarrow ABY\\ ABY\rightarrow ABD$

expanded $DB\rightarrow BD$:

$DB\rightarrow DU\\ DU\rightarrow IU\\ IU\rightarrow ID\\ ID\rightarrow BD$

expanded $DX\rightarrow Xb$:

$DX\rightarrow DP\\ DP\rightarrow LP\\ LP\rightarrow XP\\ XP\rightarrow Xb$

Finalisations rules:

$X\rightarrow a\\ AB\rightarrow aB\\ aB\rightarrow ab\\ bB\rightarrow bb$

---
Tags: formal-languages, formal-grammars, context-sensitive
---


title: Meaning of ε in NFA-ε?

text:
# Question
Title: Meaning of ε in NFA-ε?
In wikipedia NFA-ε transition function defined as follows $Δ : Q × (Σ ∪ \\{ε\\}) → P(Q)$, where $Σ$ is an alphabet and $ε$ - empty **string**. I don't understand the meaning of $ε$ in this context.

Assuming $ε$ means a sequence of symbols with length of zero, as per definition.

Alphabet $Σ$ is a set of symbols. But symbol $\neq$ sequence of symbols (string). Thus, $(Σ ∪ \\{ε\\})$ is no longer set of symbols, but a mixed set. I don't know much of set theory, but is this mixed set allowed in this context?

Also. When does NFA ε-transition happen?

1. ε-transition happens when input symbol is an empty string? Meaning, that presence of empty string is necessary condition for ε-transition .
2. ε-transition happens when there are no input symbol at all? Meaning, that presence of empty string is not necessary condition for ε-transition.

I think that the latter case, or I am wrong?

I would have avoided this confusion, if $ε$ would mean "NO\_INPUT" **symbol**, rather an empty string as per definition.

# Answer
> 1 votes
> I don't know much of set theory, but is this mixed set allowed in this context?

There's an axiom of set theory that, for any two sets $A,B$ then $A \cup B$ is also a set. So it's definitely defined.

> When does NFA ε-transition happen?

Try not to think of NFAs as actual machines, but instead focus on their mathematical definitions.

For every state $q$ of our NFA, there is some set $\epsilon CLOSE(q)$ of sets reachable from $q$ using 0 or more $\epsilon$-labelled transitions.

In an NFA without $\epsilon$-transitions, from a state $q$ and an input letter $a$, then the transition function $\delta(q,a)$ gives a set of states reachable from $q$ on input $a$, specifically all those states with an $a$-transition from $q$.

In an $\epsilon$-NFA, the states you can reach from $q$ on input $a$ is defined as to be $\\{q' \mid (q,q'') \in \delta, q' \in \epsilon CLOSE(q) \\}$. That is, it's the set of states you can get by following $a$.

The exact definitions are a bit more complicated, because you have to account for also taking $\epsilon$-transitions from whatever state you're starting at.

A word is accepted by an NFA if there's some sequence of transitions you can take to an accepting state where, when you concatenate the labels of all the transitions you take (treating the character inputs as 1-letter words), you get that word.

The point is, the meaning is just this definition. There's no "when" it happens, because it's sets and functions and relations all the way down.

> I would have avoided this confusion, if ε would mean "NO\_INPUT" symbol, rather an empty string as per definition.

We usually don't say this, because $\epsilon$ doesn't occur in the input words. (There's an infinite number of $\epsilon$s implicitly between every character of the words, but then our representation isn't unique we don't want that.) What you could do is have some special symbol which, when attached to a transition, denotes that it's a transition that can be taken without consuming input. But that's purely a definition of style: the final result is not changed.

# Answer
> 1 votes
An epsilon transition is simply a transition that doesn't consume any characters in the input string.

Taking it is optional, and it is what makes the non-deterministic finite automata non-deterministic: by allowing it to 'branch' it can 'explore' two plausible paths through the language it accepts. It is essentially just a space saving measure: DFAs (which do not permit epsilon transitions) are computationally equivalent to NFAs. There are steps to convert an NFA to an equivalent DFA, removing epsilon transitions is part of this conversion.

To explicitly draw out answers to your questions: In your example it is akin to a 'NO\_INPUT' symbol, but more like 'NO\_COST'. Think of it like this: Each edge has a 'cost' in the symbol along it that you must pay to transition along that edge. An epsilon has no cost. You don't 'spend' any characters from your input string to traverse that edge. Because of that, you now have multiple paths: Take the epsilon transition (or transitions) and spend no symbols from the input string, or 'spend' an input string along an edge. So it essentially the computation 'branches', and your NFA accepts a string if any path through it concludes in a success state.

---
Tags: automata, finite-automata, computation-models
---


# Question
Title: Vehicle Routing Problem with multiple deliveries?
I have a problem that can be reduced to the following:

> There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points" (eg. there are five places where you can pick up object A, and five places where you must deliver it). What is the optimal route?

It is similar to the "vehicle routing problem with pickups and deliveries", except that rather than delivering one item from one point to another there are multiple choices for pickup and delivery points.

Is there literature, or perhaps software, that treats this specific problem? Alternatively, can this problem be reduced to a more common variant?

# Answer
> 0 votes
It can be reduced to a TSP with an incomplete graph (i.e. with some missing edges). Each delivery "slot" is simply represented as a node in the graph, connected appropriately to the other nodes.

---
Tags: algorithms, optimization
---


# Question
Title: Complexity of Block edit distance with Swapping only
Suppose I have **distinct** letters in an alphabet $\sum = \\{a\_1,a\_2,...,a\_n\\}$. I also have two permutations of these letters, let's call them $A,B$. How can I find the Edit distance between $A$ and $B$ with block edit operations allowed?

To make it clearer, an example would be $\sum =\\{a,b,c,d \\}$. Two possible permutations are $A=\`\`abcd",B=\`\`dabc"$. The edit distance here would be $1$ because we can swap the block $\`\`abc"$ with $\`\`d"$ to get one string to the other.

Clearly, there won't be any deletions/insertions in this form of the problem, it will purely be swaps since the two strings are permutations of the same letters.

Now I know that the original edit-block problem with all operations is NP-Hard, however, would the restriction of only block swaps perhaps make this solvable in polynomial time? Most text I've read don't address this version and instead address variations of the original problem. Any help would be appreciated.

# Answer
> 5 votes
When one operation is exactly "removing a block and inserting it between two other positions", the problem of computing the string distance is known as **Transposition Distance**. It is NP-hard even if both input sequences are $p$-sequences, that is, if every letter occurs only once in each input sequence:

Laurent Bulteau, Guillaume Fertin, Irena Rusu: Sorting by Transpositions Is Difficult. SIAM J. Discrete Math. 26(3): 1148-1180 (2012)

# Answer
> 1 votes
Thanks to C Komus for providing the initial paper. After reading in the paper that he added, the authors cited another paper which can perform it if the words are permutations of each others, which is exactly my case. I found that this is indeed possible in polynomial time. $O(n^2)$ to be exact.

David A. Christie: Sorting permutations by block interchanges. Information Processing Letters, 1996, 60, 4, 165-169

---
Tags: complexity-theory, time-complexity, strings, string-metrics, edit-distance
---


# Question
Title: Decidability of languages containing bitstrings and their corresponding ones' complements
Consider strings $s \in \\{0,1\\}^\*$. Define $c\_1(s)$ to be the ones' complement of $s$; i.e., the string obtained from $s$ by inverting all of its bits. So, for example, $c\_1(000111) = 111000$. Call a language $L \subset \\{0,1\\}^\*$ *ones' complement closed*, or OCC, if $s' \in L$ $\iff$ $c\_1(s') \in L$, provided $s'$ is not the empty string. Given these assumptions, I have a few questions.

Does there exist an OCC language that is both Turing-recognizable and not decidable?

Does there exist an OCC language $L$ with the property that both $L$ is not decidable and $\overline{L}$ is Turing-recognizable?

Does there exist an OCC language $L$ that is such that neither it nor $\overline{L}$ is Turing-recognizable?

I am having some trouble answering these questions because of how limited the alphabet $\\{0,1\\}$ is. I was thinking that perhaps this alphabet alone could be used to encode Turing machines, and from there we could talk about the well-known decidable/undecidable and recognizable/not-recognizable languages involving Turing machine encodings, but I'm not sure this is possible.

# Answer
> 2 votes
Given a language $L$, you can create a language $L'$ which is equivalent in power and OCC: $$ L' = \\{ 0 x : x \in L \\} \cup \\{ 1 c\_1(x) : x \in L \\}. $$ The two languages are recursively equivalent. This means that there is a computable reduction from $L$ to $L'$ and another one from $L'$ to $L$.

Using this construction, you can now answer your own question.

---
Tags: formal-languages, turing-machines, undecidability
---


title: Need help trying to figure out DFA

text:
# Question
Title: Need help trying to figure out DFA
Can anyone please help me try to understand what will the state diagram look like for this question:

> Let $L = \\{x\_0y\_0z\_0x\_1y\_1z\_1\ldots x\_{n-1}y\_{n-1}z\_{n-1} \mid \exists n,x,y,z \\, x+y=z \land x=\sum\_{j=0}^{n-1} x\_j2^j \land y=\sum\_{j=0}^{n-1} y\_j2^j \land z=\sum\_{j=0}^{n-1} z\_j2^j \land \forall i \\, x\_i,y\_i,z\_i \in \\{0,1\\}\\}.$ Show that $L$ is regular. It is sufficient to draw a state diagram.
>
> Try to design your state diagram in a systematic way. Arrange your states in 3 columns (with 1 exception), such that before reading the $j$th bit you are in column $j$. If at this time, the DFA has to remember 2 bits, you could draw the states in lexicographical order of these 2 bits.

Any help is much appreciated. I've spent more than an hour just trying to understand the question and still could not figure it out.

# Answer
> 4 votes
The alphabet for this language is $\Sigma=\\{0,1\\}$. We also have that $x\_i,y\_i,z\_i\in\Sigma$. So, notice that $$\sum\_{j=0}^{n-1}x\_j2^j$$ is simply the decimal equivalent if we assume that the symbols of $x$ are expressed as a number in binary. Similar can be said for $y$ and $z$.

Using this, one can see that the language is effectively the those strings such that if you take every third symbol and form $x,y,z$, the numerical equivalent adds up.

For this to be true, for every $x\_i,y\_i$ and carry from the past additions, the corresponding $z\_i$ should be the correct symbol. If it were not so, then irrespective of the future symbols, we cannot have $x+y=z$, and the string can never be accepted.

So, at each iteration, the DFA needs to remember the current values of $x\_i,y\_i$ and the current carry. If the corresponding $z\_i$ is correct and the carry is $0$, it can return to the start state and continue, as this is not going to affect future considerations in any way. This is a final state as at any point when the DFA is in this state, the current sets of $x\_i$s, $y\_i$s, and $z\_i$s are such that the string would be accepted.

If the value of $z\_i$ is correct but the carry is not $0$, then the DFA goes to a different state corresponding to carry being $1$. This is not a final state as if the carry was $1$ at the end, it would imply that $x+y\ne z$ as $x,y,z$ must have the same number of symbols.

If the value of $z\_i$ is incorrect, then the symbol at that "bit" can never be corrected in the future, and the DFA can be sent to a sink state where the string is rejected irrespective of the remaining symbols.

Using the above, the DFA I have drawn (using JFLAP) is as follows:

The first column is when $x\_i,y\_i,z\_i$ have been received. $q\_0$ corresponds to a carry of $0$ and is that start and final state. $q\_7$ corresponds to a carry of $1$. The second column is the set of states when $x\_i$ has been received, and the third is when $y\_i$ has been received. Then, when $z\_i$ is received, if it matches $z\_i=x\_i+y\_i+\text{carry}$, the DFA goes to state $q\_0$ or $q\_7$ depending on the carry. Else, it goes to $q\_{14}$, which is a sink.

---
Tags: finite-automata
---


title: Myhill-Nerode and closure properties

text:
# Question
Title: Myhill-Nerode and closure properties
It is well known that regular languages are characterized by the Myhill-Nerode equivalence. For language $L$ over $\Sigma^\*$ define the equivalence $x\sim\_L y$ over $\Sigma^\*$ iff for all $z\in\Sigma^\*$ we have $xz\in L \iff yz\in L$. Then $L$ is regular iff $\sim\_L$ is of finite index, i.e., has a finite number of equivalence classes.

I know that the relation can be used to show that some languages are *not* regular, by indicating infinitely many strings that are not equivalent.

My question: can we easily use Myhill-Nerode to show closure properties of regular languages? Or should we use the "syntactic congruence" of languages?

As an example for prefix it is easy, as $x\sim\_L y$ implies $x\sim\_{\mbox{pref}(L)} y$. But how do we handle suffix, concatenation, star, mirror?

# Answer
> 7 votes
I do closure under boolean operations with the MyHill-Nerode characterisation. Never saw it done that way. A right congruence $\sim$ saturates a language $L$ if $$ u \sim v \Rightarrow ( u \in L \leftrightarrow v \in L ) $$ or equivalently iff $L$ is an union of congruence classes. We use:

**Theorem:** (MyHill-Nerode) A language is regular if and only if there is a right-congruence of finite index that saturates $L$.

Now suppose we have regular languages $L\_1, L\_2 \subseteq X^{\ast}$, and denote $\sim\_{L\_1}, \sim\_{L\_2}$ some right congruences of finite index saturating them. Then $$ u \sim v :\Leftrightarrow u \sim\_{L\_1} v \land u \sim\_{L\_2} v $$ is a right congruence (the intersection of both), and it refines both. Furthermore we have $$ \[u\]\_{\sim} = \[u\]\_{\sim\_{L\_1}} \cap \[u\]\_{\sim\_{L\_2}}. $$ Hence we have a finite number of equivalence classes. Also this gives that the intersection of equivalence classes $\[u\]\_{\sim\_{L\_1}}$ and $\[v\]\_{\sim\_{L\_2}}$ is either empty, or it has a common element $w$ and hence equals the equivalence class $\[w\]\_{\sim}$. This gives that $L\_1 \cap L\_2$ is either empty or could be written as the union of equivalence class for $\sim$. By the above theorem $L\_1 \cap L\_2$ is regular.

For $L\_1 \cup L\_2$ it is an union of equivalence classes for $\sim\_1$ and $\sim\_2$, which are themselve unions of equivalence classes for $\sim$, hence it is also regular. And for complementation, this follows as the equivalence classes partition $X^{\ast}$, hence a right congruence working for $L\_1$ works also for $X^{\ast} \setminus L\_1$. $\square$

*Additional comments:* In your question you also mentioned the canonical Nerode right congruence $$ u \equiv\_L v :\Leftrightarrow (\forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L) $$ with $L \subseteq X^{\ast}$. This is the coarsest right-congruence saturating $L$. Now maybe it might be natural to ask if we can construct the Nerode right congruence of $L\_1 \cap L\_2$ or $L\_1 \cup L\_2$ easily out of the ones for $L\_1, L\_2$, or if the resulting intersection congruence arises as some Nerode right congruence. Maybe we can find such simple formulas like $$ u \equiv\_{L\_1\cap L\_2} v \Leftrightarrow u \equiv\_{L\_1} v \land u \equiv\_{L\_2} v. $$ But the above does not hold. And to my knowledge there does not exists any simple relation. For example consider $L\_1 = (aa)^{\ast}$ and $L\_2 = a(aa)^+$, then we have $$ L\_1 \cap L\_2 = \emptyset, \qquad L\_1 \cup L\_2 = X^{\ast} \setminus \\{a\\}. $$ Now $\equiv\_{L\_1} \cap \equiv\_{L\_2}$ has at least four congruence classes, as it refines $\equiv\_{L\_2}$ which has exactly four congruence classes. But $\emptyset$ has precisely one class, and $X^{\ast} \setminus \\{a\\}$ has three (could all be easily seen by using minimal complete automata).

**EDIT (2019.08.18).** The mirror and suffix operation are related to the left congruence $$ u \equiv^L v \Leftrightarrow \forall w \in X^\* : wu \in L \leftrightarrow wv \in L. $$ If $\equiv^L$ has finite index, similar as for the prefix-operation and the right-congruence, $\equiv^{\operatorname{suffix}(L)}$ has finite index. And $u \equiv\_L v$ iff $\operatorname{mirror}(u) \equiv^{\operatorname{mirror}(L)} \operatorname{mirror}(v)$; and as the mirror operation is a bijection on $X^\*$ the last equation gives that $\equiv^{\operatorname{mirror}(L)}$ has finite index iff $\equiv\_L$ has finite index (note that the left congruence has the same index as the right congruence for the mirrored words, but in general a right congruence for $\operatorname{mirror}(L)$ might have exponential many more classes as is shown by standard contructions from automata theory).

So these operations are handled if we can show that both congruences have finite index at the same time or not. For this lets look at the syntactic congruence $$ u \equiv\_{S(L)} v \Leftrightarrow \forall x,y \in X^\* : xuy \in L \Leftrightarrow xvy \in L. $$ This congruence refines both congruences above, hence if it is finite, both congruence above are also finite. It is $u \equiv\_{S(L)} v$ iff for all $w \in X^\*$ we have $\[wu\]\_{\equiv\_L} = \[wv\]\_{\equiv\_L}$, hence we have a well-defined and injective map from the $\equiv\_{S(L)}$-equivalence classes to the transformations on $\\{ \[w\]\_{\equiv\_L} : w \in X^\* \\}$, and if the latter is a finite set, the set of those transformations is finite too, which implies that $\equiv\_{S(L)}$ is of finite index. So in total we have that $\equiv^L$ has finite index if $\equiv\_L$ has finite index, the reverse is implied similar.

# Answer
> 6 votes
The equivalence classes of the Myhill-Nerode relation are also the states of the minimal DFA for the language. So whatever is easy to show using DFAs, you can convert to a proof which uses the Myhill-Nerode point of view. Wherever you need NFAs, you can expect the proof to get more complicated.

But the correct answer is: try it out for yourself! That's how research is done.

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


# Question
Title: Recover NLFSR description from given output
Given Fibonacci's Nonlinear Feedback Shift Register output, how can I recover the description (nonlinear feedback function and current seed)?

The clean output of consecutive and unmodified is large and the generator is available to ask for next values. The source code of PRNG is not available, the seed is unknown.

For the linear case there is already known Berlekamp-Massey (or Reed-Sloane) algorithm yielding the shortest polynomial. Is there a similar method for nonlinear case?

# Answer
> 4 votes
Normally we evaluate PRNGs under the model where the source code is available and fully known, and where the output is a deterministic function of the seed. This leaves multiple possibilities for how to build a NLFSR: we can have a fixed feedback function (hardcoded in the source code), and use the seed to specify the initial state; or we can use part of the seed to generate a feedback function and use the remainder of the seed to specify the initial state.

If the feedback function $f$ is known, it is trivial to predict the next outputs of the NLFSR from the past $n$ bits, where $n$ denotes the width of the state. Also, it is often possible to predict past output, but this depends on the feedback function and on $n$.

If $f$ is not known but derived from part of the seed, then the procedure depends on the details of how it is derived. There are $2^{2^n}$ possible feedback functions $f:\\{0,1\\}^n \to \\{0,1\\}$. If we use $2^n$ bits from the seed so we can sample uniformly at random from the set of all functions (i.e., all $2^{2^n}$ functions are possible and equally likely), then the PRNG is not very useful in practice. After seeing about $O(2^{n/2})$ bits of output, you can usually distinguish the output of the PRNG from true-randomness and predict future outputs, because (by the birthday paradox) it is likely that the internal state will repeat at some point in there and the generator will enter a cycle (of length at most $O(2^{n/2})$). Of course this design requires more than $2^n$ bits of true randomness as input, and can only produce $O(2^{n/2})$ bits of output before its output is recognizable, so this is a fairly crummy PRNG; you've basically wasted the randomness, and you might as well have just used the true-randomness directly without a PRNG.

Alternatively, perhaps you had in mind that part of the seed is used to select a feedback function $f$, via some algorithmic process -- but not all feedback functions are possible or equally likely. Then the ability to distinguish, predict future outputs, or recover the seed is dependent upon the details of that algorithmic process. However, we can say this much. The output of the PRNG can be distinguished from truly-random after $O(2^{n/2})$ outputs, for reasons sketched above (due to the birthday paradox).

The period of a NLFSR is determined by the function $F:\\{0,1\\}^n \to \\{0,1\\}^n$, defined by

$$F(x\_1,\dots,x\_n) = (x\_2,\dots,x\_n,f(x\_1,\dots,x\_n)).$$

Let me mention some typical cases.

First, if $f$ satisfies $f(0,x\_2,\dots,x\_n)=f(1,x\_2,\dots,x\_n) \oplus 1$ for all $x\_2,\dots,x\_n$, then $F$ will be bijective, the period of the NLFSR will typically be about $2^n$ (if $f$ has no other regularities), and given about $2^n$ bits of output you'll be able to predict all future outputs (since it cycles) or recover the original seed. Also, you'll be able to distinguish the output of the NLFSR from truly random with about $O(2^{n/2})$ bits of output (by the birthday paradox, a true random stream will have some $n$-bit value repeat twice within that range, but that'll never happen in the output from this type of NLFSR).

Second, if $f$ has no regularities or patterns and is basically random, then $F$ will fail to be bijective, and the period will typically be about $2^{n/2}$. So, after $O(2^{n/2})$ bits of output you'll be able to predict all future outputs (since it cycles), and you'll be able to distinguish the output of the NLFSR from truly random with about $O(2^{n/2})$ bits of output (a true-random stream won't cycle but this NLFSR will).

If the feedback function $f$ is chosen randomly from a small list of possibilities (e.g., the ones listed in the paper you cited), then it is easy to recognize output from such a PRNG: just try each possibility in turn, and use the method described for the case where $f$ is known. If there are $m$ possibilities for $f$, then $n+\lg m+O(1)$ bits of output suffice to infer which possibility is correct and verify that the output is consistent with such a NLFSR with high probability.

What this fails to account for is other attacks, which try to take advantage of structure in $f$. For instance, suppose $f$ is chosen to have small circuit size. Then it may be possible to recover $f$ with many fewer than $2^n$ bits of input: each consecutive $n+1$ bits of output gives us a known input-output pair $(x,y)$ for $f$ (namely, $x = $ the first $n$ bits, and $y =$ the $n+1$st bit), and given many such pairs, we can try to find a function $f$ that is consistent with all the pairs and has low circuit complexity. That might be enough to uniquely determine the function $f$; if so, it may or may not be possible to recover it explicitly within a reasonable amount of computation (e.g., with BDDs, Karnaugh maps, or other methods).

Since the question is rather vague, that makes it rather hard to assess the possibilities for the latter kind of method. So, I'll just end with a disclaimer that the analysis above might overestimate the number of bits of output needed to recognize/detect this kind of LFSR.

# Answer
> 1 votes
NLFSRs are intentionally designed/ used for cryptography to be highly "secure" and resistant to "weakness" aka finding their generating parameters *except* through brute force. this is essentially the process of "cryptoanalysis/ decryption of a PRNG" which is studied extensively in cryptography. but there is at least one case study for consideration. the KeeLoq code is based on a NLFSR and is used in a lot of automotive keylock systems, and therefore has been subject to heavy academic analysis/ experimental attacks. while some weaknesses have been found nevertheless it looks like most of the attacks are basically brute force, although there is some use of FPGAs to streamline the hardware attack. wikipedia notes Nicolas Courtois attacked KeeLoq using sliding and algebraic methods. see also \[1\]

\[1\] Period, correlation and auto-correlation of non-linear feedback shift registers based sequences / Crypto stackexchange

---
Tags: algorithms, pseudo-random-generators
---


title: Pumping Lemma: 1^n^2 is not regular

text:
# Question
Title: Pumping Lemma: 1^n^2 is not regular
I am attempting to prove via the pumping lemma that $1^{n^2}$ is not a regular language. I started with

$w = 1^{p^2}$

I then divided $w$ into $xyz$, where:

$x = 1^{l}$

$y = 1^{m}$

$z = 1^{{p^2}-l-m}$, where $l+m \le p$ and $m \ge 0$.

Now, when I choose $i=2$ in order to get $xy^2z$, I end up with:

$1^{{p^2}+m}$, since $0 \> m \le p $, the sum $m+p^2$ could certainly not be a square because the difference between $p^2$ and the next square is always greater than $p$ for all natural numbers.

Q.E.D

However, even if the basic logic of the proof is right, it does not seem as if my conclusion is as strong as it should be. Is there a more formal, proof-like manner to reach my conclusion with the same $s$ and $xyz$?

# Answer
> 1 votes
Your proof is correct, but you could elaborate your arguments if you wish.

We have $m\gt 0$ (typo in your question I think, you have used $\ge$) and $l+m\le p$. As $l\ge0$, $0\le p-m\implies m\le p$

$$m\gt0\implies p^2+m\gt p$$ $$\begin{align}m\le p&\implies p^2+m\le p^2+p\lt p^2+2p+1=(p+1)^2\\ &\implies p^2+m\lt (p+1)^2\end{align}$$

$p\lt 2p+1$ is true because $p\ge1$.

Thus, $p^2+m$ lies strictly between two consecutive squares, and hence cannot be a perfect square.

---
Tags: proof-techniques, pumping-lemma
---


# Question
Title: Ehrenfeucht-Fraïssé games, possible mistake in example
I was reading up on Ehrenfeucht-Fraïssé and came by this example at http://www.math.cornell.edu/~mec/Summer2009/Raluca/lesson3.html

Shouldn't there be a line between b4 and b2 (or b3 and b1), otherwise I don't see how the duplicator has a winning strategy in 3 rounds. Is this a mistake or ami I missing something?

thank you.

# Answer
> 4 votes
Spoiler wins the $3$-move EF game by picking $a\_1$, $a\_2$, $a\_3$ in any order. You can confirm this by observing that there is a formula of quantifier rank at most $3$ that is satisfied by $A$ but not by $B$, namely:

$$ \exists x\exists y\exists z \ .\ x\neq y \wedge y \neq z \wedge z \neq x \wedge r(x, y) \wedge r (y, z) \wedge r(z, x) $$

where $r$ is the adjacency relation. Since $A$ has $3$ vertices and $B$ has $4$, Spoiler will also win any $k$-move game for $k\ge 4$, probably the question meant to ask about the $2$ and $3$-move games respectively, instead.

---
Tags: first-order-logic
---


# Question
Title: Tight instance for unweighted maximum coverage problem?
The maximum (unweighted) coverage problem is defined as follows:

* **Instance**: A number $k$ and a collection of sets $S = \\{S\_1, S\_2, \ldots, S\_m\\}$.
* **Objective**: Find a subset $S^{'} \subseteq S$ of sets, such that $\left| S^{'} \right| \leq k$ and the number of covered elements $\left| \bigcup\_{S\_i \in S^{'}}{S\_i} \right|$ is maximized.

This problem is NP-hard. I am trying to find a counterexample when the greedy algorithm fails but I failed. Especially, can you find a family of instances when the greedy algorithm always fails? (Or at least one simple instance?)

* **The greedy algorithm:** at each stage, choose a set which contains the largest number of uncovered elements.

I found a family of instances here but it was for the weighted case and I cannot transform it to the unweighted case.

# Answer
> 4 votes
Here is one example: take the universe $$U=\\{u\_1,\dots,u\_n,v\_1,\dots,v\_n\\}$$ $S\_i=\\{u\_i,v\_i\\}$ for $i=1,\dots,n$ , and $S\_{n+1}=\\{u\_1,\dots,u\_n\\}$, $m=n+1$, $k=n$

---
Tags: algorithms, reductions
---


# Question
Title: DFA - Accept all strings that does not contain a certain substring
So I have been trying to create a Deterministic Finite Automaton(DFA) in Jflap that accepts all strings from the alphabet {a, b, c} except those that contain the substring "abc". However i keep running into issues where certain strings that should be allowed aren't, such as "acbc". Do you have any tips or tricks that can be used to get around these kind of issues?

## DFA that accepts any string that contains substring "abc" below

# Answer
> 2 votes
This is the inverted DFA of Image 2 which should accept all string combinations of the language{a,b,c} that do not contain the substring "abc"

## Final Automaton

---
Tags: automata, finite-automata, substrings
---


# Question
Title: Sort complexity expressed via distinct number of elements
I am reading Probabilistic counting algorithms for database applications. In the introduction an algorithm for finding an intersection is specified:

Sort A, search each element of B in A and retain it if it appears in A.

It is claimed that if a, b are number of elements in A and B, and $\alpha, \beta$ are the number of distinct elements in A, B then the complexity of this algorithm is $O(a\log\alpha + b\log\alpha)$. My question is, why the sorting of A is only dependent on the number of distinct elements? Is there some kind of algorithm I am not aware of? If so, why the same algorithm could not be used for the second strategy? The second strategy is:

Sort A and B, use merge-like operation to discard duplicates.

For this algorithm the complexity is $O(a\log a + b\log b + a + b)$ which makes sense to me.

# Answer
> 3 votes
You can use a balanced binary search tree to sort $A$ in time $O(a\log\alpha)$ by going over the elements of $A$, for each element searching whether it already appears in the tree, inserting it if it isn't already there. You can then perform the second stage in $O(\log \alpha)$ per element of $B$, for a total of $O(b\log\alpha)$.

If you are allowed to use hashing on the elements of $A$ and $B$, then you can use a dynamic hash table to compute the intersection in expected $O(a+b)$ time by using a similar strategy.

# Answer
> 0 votes
Observe that we can eliminate duplicate elements in $A$ in time linear in $a$. So, the process of eliminating elements and then sorting is $O(a + \alpha \log \alpha)$ which I claim is $O(a \log \alpha)$ for $a \> \alpha$.

The runtime you give for your algorithm is indeed $O(a \log a + b \log b)$ since the linear terms you give are taken by the poly log terms. To see this, observe that $2 a \log a \> a \log a + a$ for all sufficiently large $a$.

---
Tags: algorithms, complexity-theory, sets
---


# Question
Title: Algorithm for getting symetric vertex sets of undirected graph
For my application problem, I am searching for **an algorithm that can find all symmetric vertex sets of an undirected labeled graph.**

My definition of symmetric vertex set is: Let $G$ be a graph with vertex set $V$ and edge set $E = \\{u,v\\}, u,v \in V$. If $S \subseteq V$ and there exits an isomorphism $f$ on this graph such that for every $v\in S$, we have $f(v) \in S$, then $S$ is called a symmetric vertex set.

I have searched some graph matching algorithms, but have gotten no clue so far. I am wondering if any one can give me a hint, I will work on it.

# Answer
You want to know the orbits of the action of the automorphism group of a graph on its vertices. This is equivalent to graph isomorphism, for which no really simple algorithms are known. Practical graph isomorphism algorithms, which work fast in practice, are known – check nauty for example. Apparently nauty can compute the automorphism group directly, from which you can easily compute the orbits of its action on the vertices.

**Solving GI using your task.** Given *connected* graphs $G\_1,G\_2$, we want to know whether they are isomorphic. Compute the orbits, and check whether any of them mixes vertices from $G\_1$ and $G\_2$.

**Solving your task using GI.** Given a graph $G$ and two vertices $x,y$, create two copies of $G$ and attach a long path to $x$ in one of them and to $y$ in the other. The two vertices belong to the same orbit if these graphs are isomorphic.

The second reduction involves $n^2$ invocations of GI, whereas $\log B\_n \approx n\log n$ (here $B\_n$, the $n$th Bell number, is the number of partitions of $\\{1,\ldots,n\\}$). This means that any reduction needs $\Omega(n\log n)$ invocations of GI, and suggests that my reduction can be improved.
> 5 votes

---
Tags: graphs, graph-isomorphism, transitivity
---


title: Petri Net Verifier

text:
# Question
Title: Petri Net Verifier
Imagine I can specify a certain process as a Petri Net. Is there any good software, open source or not, that can verify my process against some conditions I declare (or code) in some language?

In case not, is there an open source software that does at least simulations?

# Answer
It's not really a field I know much about, but I doubt it.

Model-checking problems get very hard (sometimes very undecidable) very fast. Whether what you ask is faisable at all depends on the kind of statements you are interested in checking and on what restrictions on the Petri nets structure you are willing to impose.

On general nets, all interesting questions (e.g. marking reachability) are $\text{EXPSPACE}$-hard. General model-checking is undecidable even for very weak branching-time temporal logics; several interesting fragments of linear-time logics are decidable but at least as hard as the reachability problem, i.e. $\text{EXPSPACE}$-hard.

Software recommendations are off-topic here, but I'm sure plenty of simulators are available online.
> 0 votes

---
Tags: software-verification, petri-nets
---


# Question
Title: Decidability of checking whether all words accepted by a TM have an even number of 1s
Let $\Sigma = \\{0,1\\}$, and consider the language $$L = \\{\langle M \rangle \mid M \text{ is a TM and } L(M) \text{ is a subset of } Σ^\* \text{ and all strings in this set have an even number of 1s}\\}.$$

I think $L$ is undecidable. But I am stuck on proving it. I think it is equivalent to prove $L = \\{\langle M \rangle \mid M \text{ is a TM and } L(M) \text{ is a specific set with an even number of 1s}\\}$ is undecidable. How can I do some reduction for it?

# Answer
> 2 votes
First, it can be shown easily by Rice's theorem.

Alternatively, you can show a reduction from $\overline{HP}$ as follows:

$$f(\left\< M \right\>,x)=\left\<M\_x\right\>$$

$M\_x$ on input $w$:

1. run $M$ on $x$ for $|w|$ steps.
2. if M stopped then accept.
3. if the number of 1's in $w$ is even then accept, otherwise reject.

I'll let you verify the correctness.

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


title: Are semantic networks ontologies?

text:
# Question
Title: Are semantic networks ontologies?
I struggle with few definitions in knowledge representation and seek credible help to distinguish between them. I have been searching on wikipedia and many websites for the difference between ontologies and semantic networks (not to be confused with semantic web). While the wikipedia page on semantic network never refer to ontologies, they seem extremely similar and have similar application in CS.

My guess is that semantic network are a type of ontology adapted for research on AI. However, I don't know the difference between both. So my question is simply:

**Are semantic networks ontologies?** If so, are they synonym? or what are the distinctions?

# Answer
> 3 votes
Semantic Networks are in no way the same as ontologies. The accepted answer is therefore very misleading. Semantic networks (Quillian 1968) and semantic frames (Minsky 1975) emerged earlier than ontologies, and they were lacking a formal semantics despite the fact that they had semantic in the name. This is some kind of a fun fact among logicians: a formalism does not have semantics just because it has it in the name. This has been a basis for a systematic and formal study of ontology languages. Overall, the difference is that ontologies have well-defined, formal semantics whereas semantic networks don't. Let me support this by quoting from "The Description Logic Handbook" (Baader et. al.):

*"Owing to their more human-centered origins, the network-based systems were often considered more appealing and more effective from a practical viewpoint than the logical systems. Unfortunately they were not fully satisfactory because of their usual lack of precise semantic characterization."*

For more details, please see The Description Logic Handbook, which also contains such historical notes. Currently, ontology languages are much more sophisticated than simple terminologies and encompass a rich logical structure which can not be compared to a network, or so...

# Answer
> 10 votes
A semantic network is a **graphic notation** for representing knowledge in patterns of **interconnected nodes and arcs**. It is one way for **knowledge visualization** and presentation. It was used firstly for for artificial intelligence and machine translation in computer science. What is common to all semantic networks is a **declarative graphic representation** that can be used either to represent knowledge or to support automated systems for reasoning about knowledge.

Ontology is a **representation vocabulary**, specialized to some domain or subject. It is a representation of a set of concepts within a domain and the relationships between those concepts. It is used to reason about the properties of that domain, and may be used to define the domain.

You can find more in references as (specially 4):

1) Sowa, John F., ed. “**Principles of Semantic Networks: Explorations in the Representation of Knowledge**”, Morgan Kaufmann Publishers, San Mateo, CA, 1991.

2) Noy N.F., McGuinnes D. L. “**Ontology Development 101: A Guide to Creating Your First Ontology**”. Stanford Knowledge Systems Laboratory Technical Report KSL−01−05 and Stanford Medical Informatics Technical Report SMI−2001−0880, March 2001.

3)María Auxilio, “**An Overview of Ontologies**”, Center for Research in Information and Automation Technologies Technical Report, Interactive and Cooperative Technologies Lab, Universidad De Las Américas Puebla, México, March 2003.

4) ABDEL-BADEEH M. SALEM, MARCO ALFONSE "**Ontology versus Semantic Networks for Medical Knowledge Representation**", ICCOMP'08 Proceedings of the 12th WSEAS international conference on Computers, 2008.

---
Tags: terminology, knowledge-representation, ontologies
---


# Question
Title: Can I have actions that, if taken, cannot be taken again in the following N timesteps?
I'm trying to train a load-balancing system with reinforcement-learning (RL) s.t. the incoming jobs are queued evenly at the available servers. The system will not be able to directly dispatch the jobs, but it will only offer suggestions to use a set of servers over another. The system will also be capable of reducing the speed at which new jobs arrive and at each time step, to reduce the queue lengths. The agent must decide whether to change this speed or keep it constant.

Changing the speed at time T, however, disables any other changes until time T+N, with N constant (basically, we need to prevent speed changes at every time-step).

Are these actions an obstacle in training the system? All RL systems I know only deal with actions that can be taken at every time step and don't put any constraints in future use of the action. Is this a limitation of RL agents?

# Answer
> 2 votes
This is not a limitation. Which actions are valid can depend on the current state of the system.

To enforce your requirement (changing speed at time T means you can't change again until time T+N), you can add additional information to the state: basically, add how long ago was the last change (where if it's more than N steps ago, you don't keep track of how long, just that it was long enough that a change is now allowed).

---
Tags: reinforcement-learning
---


# Question
Title: How to detect Farkas or MPEG4 FDP points on image with a face?
## Brief problem description

I'm using a Basel Morphable Face Model, which was labeled with MPEG4 and Farkas landmarks. I can generate different faces, use different lighting conditions, rotations, perspective etc.

I want to use it to train an algorithm in order to find these landmarks on real pictures further.

## More strictly

Given a labeled set of images (with fixed size, if it's critical), I want to get a function $q\left( x \right)$ (where $x$ is an image), which will minimize loss expectation (Bayes' task)

$$E = \sum\limits\_{x \in X, k \in K} P\left( k \mid x \right) \cdot W\left( k, q\left( x \right) \right)$$

$k$ is a tuple of feature points' coordinates like $\<(x\_1, y\_1), (x\_2, y\_2), \dots\>$.

Loss function is either

$$W\left(k, k'\right) = \sum\limits\_{i=1}^n ||k\_i - k\_i'||^2$$

or

$$W\left(k, k'\right) = \sum\limits\_{i=1}^n(1\\; if\\; ||k\_i - k\_i'|| \> \Delta\\; otherwise\\; 0)$$

Maybe there is a better problem description, and loss expectation minimization is not suitable for this task?

## Details

I guess, there are more specific algorithms for this issue than Brute Force (estimate probabilities by training set and use them to find landmarks on input images) or Artificial Neural Networks.

Why not ANN: the problem "as is" is incredibly hard. I have $44$ points, most of which have symmetric ones (so, it's something between $60$ and $80$). Given image $100×100$, I have at least $10'000^{60}$ different solutions and should find the best one (or weighted average in case of $l^2$ loss function). $10^{240}$ is a huge number. Add probabilities estimate to this Math carnival, and you'll get a problem of estimating probability function for $10'000$ dependent random variables via each image of the training set. So, if some general approach will work fast, I'm not sure that it will be accurate enough. The new problem will occur — what exactly will we lose when ANN will be applied?

Maybe two-dimensional context-free grammars can solve this, and I just need a proper representation to take scale and rotations into account.

Maybe the problem can be stated in terms of constraint satisfaction problem and solved efficiently.

## Question

Which algorithms you can recommend for my purpose?

# Answer
In the simplified special case where each image $x$ has a single correct labelling $k=\kappa(x)$, this becomes just a regression problem: you want to find a function $q$ that minimizes the risk

$$\mathbb{E}\[||q(X)-\kappa(X)||^2\],$$

where $X$ is a random variable distributed according to some distribution on faces. One way to solve this is to build up a training set of pairs $(x\_i,k\_i)$ where $x\_i$ is a face and $k\_i$ is its label, and then minimize the empirical risk

$$\sum\_i ||q(x\_i)-k\_i||^2.$$

This then becomes an optimization problem: find parameters for $q$ that minimize the empirical risk. You could use any of a number of different methods for regression, based on what structure you think $q$ might have. For instance, you could use a convolutional neural network.

Your problem is a more general version of this, where we want to minimize the risk

$$\mathbb{E}\[\ell(X,q(X))\],$$

where

$$\ell(x,y) = \int p(k|x) ||y-k||^2 dk.$$

I will assume you have an efficient way to compute $\ell(x,y)$ for any particular $x,y$ (whether by integrating analytically using some expression for $p(k|x)$, or by sampling many $k$ from the distribution $p(k|x)$ and taking the average value of $||y-k||^2$). If this is the case, one approach is again to build a training set of faces $x\_i$, each with a known distribution $p(k|x\_i)$, and then minimize the empirical risk

$$\sum\_i \ell(x\_i,q(x\_i)).$$

This is just an optimization problem, where you try to find parameters for $q$ that minimize the empirical risk. Assuming you have an efficient way to compute $\ell(\cdot,\cdot)$, you can proceed as before and use any standard method for regression (e.g., a convolutional neural network).
> 1 votes

---
Tags: features, facial-recognition
---


# Question
Title: Construct DFA accepting strings ending with '110' or '101'
Let the alphabet be $\Sigma=\\{0,1\\}$. I want to construct a DFA which accepts strings ending with either '110' or '101', additionally there should be only one final state.

I have a solution with more than one final state, but cannot come up with a solution which has only one final state.

# Answer
There cannot be a single final state. Consider any DFA for the language, and let $\sigma\_{110},\sigma\_{101}$ be its states after reading $110,101$ (respectively). Clearly $\sigma\_{110},\sigma\_{101}$ are accepting states. Moreover, they cannot be the same state since $1101$ is in the language but $1011$ is not.
> 5 votes

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


# Question
Title: Decision Problem vs. Optimization Problem
Is the following statement correct?

If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.

# Answer
We don't know that $\mathrm{P}\neq\mathrm{NP}$ so we don't know that the decision problem itself can't be solved in polynomial time!

But, under the assumption that $\mathrm{P}\neq\mathrm{NP}$, the optimization version of an $\mathrm{NP}$-complete problem can't be solved in polynomial time. If we could, for example, compute the shortest travelling salesman tour in polynomial time, we could certainly tell in polynomial time whether there's a tour of length at most $d$
> 2 votes

---
Tags: complexity-theory, np-complete, decision-problem
---


# Question
Title: Why is it that any graph traversal method can be described as pre-order, in-order, or post-order? What do those terms mean?
There are several graph traversal algorithms in computer science ( vis. depth first, breadth first, etc. ). Furthermore, each of these algorithms can be implemented in pre-order, in-order, and post-order.

What do those terms mean? How do I properly categorize an algorithm as pre-order, in-order, or post-order?

# Answer
> 1 votes
Take a binary tree with the following structure:

A traversal algorithm that considers every node in a tree must consider each node in some order. It might touch the nodes in this order: 2, 1, 3. Or this order: 1, 2, 3. And so on.

We can categorize these nodes into groups for convenience. Let us say that Node 1 is the Parent Node while Node 2 and Node 3 are Children of the Parent.

When we use terms like "pre-order", "in-order", or "post-order", we are really describing *the order in which our implementation of an algorithm touches the parent node*.

For example, an algorithm performs a pre-order traversal of the graph above if it touches the parent node *before* the child nodes. ( vis 1, 2, 3 )

An algorithm performs an in-order traversal of the graph above if it touches the parent node *in* between the child nodes. ( vis 2, 1, 3 )

An algorithm performs a post-order traversal of the graph above if it touches the parent node *after* the child nodes. ( vis 2, 3, 1 )

So, when we describe an algorithm as having a particular order, we aren't necessarily describing the algorithm--but rather we *are* describing the *implementation* of the algorithm.

For example, what if we want to implement Depth-First Search (DFS) of a more complicated graph?

Here's a larger graph traversed with a pre-order implementation of DFS:

Let us say that B and G are children of F, but none of the other nodes are considered children of F.

Notice that--given that definition--every parent node is processed before it's children. There might be several nodes processed in the course of doing that, but--no matter which parent node you check, it is guaranteed to be processed before its children.

The same goes for in-order traversal ( every parent is guaranteed to be processed *in between* its children ):

And post-order traversal ( every parent is guaranteed to be processed *after* each of its children ):

Note that all of the above are different implementations of the same algorithm, namely Depth-first Search. So, we have taken one algorithm and implemented it three different ways, each handling parents in a different order relative to their children.

In the same way, any graph traversal algorithm can be categorized as pre-order, in-order, post-order--or possibly none of the above. These terms merely describe the order in which parent nodes are processed relative to their children.

Note that the Wikipedia entry on tree traversal describes several implementations of several traversal algorithms, but is able to categorize all of these algorithms in terms of the order in which they process parents relative to their children.

---
Tags: trees, search-trees, graph-traversal, order-theory
---


# Question
Title: DFS algorithm and how do I show/put it into practice?
I'm new to DFS algorithm and I'm trying to figure it out.

The main concepts I get from it is that you have a stack of nodes, and they have a value, and can contain children-nodes (Even called branches or leaves) that can contains nodes with values.

So let's say that I have a Tree containing 15 nodes like this.

I would understand that the algorithm goes A-N-O-B-D-J-L-M-K-C-E-F-H-G-I, If you were to go in alphabetic order.

My confusion is this how to put this algorithm into practice **(such as coding it)**. How should I see this tree like (Array, List?)

And if some of the children are connected to each other can it still be a DFS algorithm?

# Answer
The first thing you need to do is pick a *data structure* \- i.e a representation for your node graph. For this I suggest you pick up any undergraduate-level book on data structures and read it carefully, and choose something appropriate. For example, given the tree above, I would represent each node with a record containing whatever data is to be stored in that node *(e.g the name - A, B, etc)* plus a list of (pointers to) child nodes. E.g your root would have the list {A, B, C}, node A would have the list {N}, node J would have the list {K, L, M}, and so on. Each childless node ('leaf') would have an empty list.

Then you code your DFS procedure, which you may find easier to do if you use recursion to process children (although there are ways to make this non-recursive if you insist). Regardless of implementation, the *core behavior* of DFS is: To process each node, you must do something with the node, then scan the list of children and process each child -and its entire subtree- before processing the next child. You can get different effects according to whether you process each node before its children, or after *\[if each node has at most two children AND explicitly distinguishes 'left' child from 'right' child, then there is also the option of processing each node -between- left and right\]*.

And yes, you can still perform DFS if there are cross-connections. The key new thing to do here is to keep track of whether the node you are about to process *has already been processed*; generally what you will want to do in that case is skip that node and go back up to the parent. This is particularly true if 'children' really means 'neighbors', so the edges between nodes aren't *directed*; then you really need to avoid running in cycles.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times
I apologize for the long title, but I really didn't know how to write it different without lacking informations about the content.

I recently had an university exam about Parallel Algorithms. One exercise asked me to write an algorithm to determine if the elements of an array, let's call it `A`, were repeated an equal number of times.

For example:

1) `A = 1 8 8 1 8 1 1 8` : the answer is yes, every number is repeated 2 times.

2) `A = 7 8 8 5 5 4 7 8` : the answer is no.

I had to write the algorithm for a particular model of parallel computing, a PRAM: the model required me to use some techniques to avoid read/write conflicts, and other problems, but this is not relevant. What I ended up with was a new array, let's call it `B`, which I can define as follow: `Given the array A, B[i] contains the number of repetitions of the element A[i] within A.`

For example:

1) `A = 1 8 8 1 8 1 1 8`

`B = 4 4 4 4 4 4 4 4`

2)`A = 7 8 8 5 5 4 7 8`

`B = 2 3 3 2 2 1 2 3`

As you might think and expect, the only thing left to do would be to check if every element of `B` is equal to the other, but.. it turns out I'm masochist, and the pressure of the exam (plus I had a bit temperature) led me to take another path. Moreover, comparing elements of an array is not immediate using this computing model.

So, to check if all the elements of `B` are the same, I summed all of them and divided the result by the number of elements of `B`: if the result was equal to an element of B (for example the first, `B[0]`) then the algorithm returned `true` (`false` otherwise).

Taking the example above:

1) `sum = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 32` --\> `32 / 8 = 4 = B[0]` --\> Yes.

2) `sum = 2 + 3 + 3 + 2 + 2 + 1 + 2 + 3 = 18` --\> `18 / 8 ≠ 2 = B[0]` --\> No.

I know it's absurd, but that's what I came up to.

I checked this approach with a lot of different combinations of arrays/numbers, and it seems to work. Thing is, I'm having an hard time in finding a (mathematical) proof that the algorithm is correct. Besides the result of the exam, which I still don't know yet, I'm very interested in knowing if there's some mathematical proof/explanation which states that this approach is correct or not, and that's why I need an help.

I hope I have posted the question in the right StackExchange site. If not, please redirect me to the right site.

Thank you in advance.

# Answer
> 11 votes
No, your algorithm doesn't work. Consider if the array A is

A = \[1 1 1 1 1 2 2 3 3 3 3 3 3\].

Then the array B will be

B = \[5 5 5 5 5 2 2 6 6 6 6 6 6\].

The sum of B will be 65, and the length of B will be 13, so after division, we'll get the number 5. This is equal to the first element of B, so your algorithm will output "Yes". Nonetheless, not all elements of B are the same, and the correct answer is "No". So, your algorithm gives the wrong output on this case.

Nice try, though! Figuring out how to build B was probably the hardest part of this problem.

---

How I found this: I couldn't find a counterexample with two distinct numbers, so next I tried with three distinct numbers. Let $u,v,w$ denote how often each of those numbers appear. Then the array will have length $u+v+w$, and B will contain the value $u$ repeated $u$ times, the value $v$ repeated $v$ times, and $w$ repeated $w$ times, so the sum of elements of B is $u^2+v^2+w^2$. We can find a counterexample if we can find a solution over the positive integers to the Diophantine equation

$${u^2 + v^2 + w^2 \over u+v+w} = u$$

such that $v\ne u$ or $w \ne u$. This is equivalent to

$$u^2 + v^2 + w^2 = u(u+v+w),$$

where $u,v,w$ are positive integers and either $v\ne u$ or $w \ne u$. I then picked a few small values of $u$ and tried solving this Diophantine equation using Wolfram Alpha. The first solution I stumbled across was $u=5$, $v=2$, $w=6$, but there are many others as well. In retrospect I guess I could have simplified further to

$$v^2 + w^2 = uv + uw$$

but I didn't notice and it turned out not to matter.

# Answer
> 5 votes
\[2,2,5,5,5,5,5,6,6,6,6,6,6\] is a counterexample.

how I found that:    (The last step of this was a Python script.)  For them to *not* all be equal, there need to be at least two distinct numbers that appear.  However, averages are *strictly* between the min and the max, so to pass your criterion there must be at least three distinct numbers.  I simply figured there ought to be a counterexample with only three distinct numbers.  For the reason I gave two sentences ago, with just three distinct numbers, one only needs to check for whether-or-not the average is the middle number.  With that observation, I wrote a Python script to try triples with respect to the lexicographic order of \[sum,largest,middle,smallest\], and the array I gave corresponds to the smallest counterexample that script found.

---
Tags: algorithms, algorithm-analysis, correctness-proof
---


# Question
Title: Size of constant depth circuit for digital comparator?
> Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers?

Two $n$-bit binary numbers can be compared using a digital comparator circuit. The straightforward way to implement such a circuit is to compare the high-order bits; if they are the same then continue to compare the second most significant bits, and so on. This circuit has size (measured in the number of gates) that is roughly quadratic in $n$, with linear depth. By standard arguments, this can be folded up into an equivalent circuit of roughly the same size that has logarithmic depth (in $n$).

In fact, *constant* depth circuits of size $O(n^2)$ are sufficient for a digital comparator, if unbounded fan-in gates are allowed: see Heribert Vollmer's *Introduction to Circuit Complexity* (Exercise 1.4). Is a tight lower bound known?

# Answer
Comparison can be implemented by subtracting twos-complement numbers and then testing whether the most significant bit is 0 or 1. Subtraction can be implemented as addition ($x-y = x + \overline{y} + 1$, where $\overline{y}$ is obtained by flipping all bits of $y$). Addition can be implemented using carry-lookahead methods.

If you put all this together, I think you get a comparison circuit that uses $O(n)$ gates and has constant depth.

In particular, let $g\_i = a\_i \land b\_i$ ("generate"), $p\_i = a\_i \lor b\_i$ ("propagate"), $q\_i = p\_{i+1} \lor \cdots \lor p\_{n-1}$, $t\_i = g\_i \land q\_i$, and $c\_{n-1} = t\_0 \lor \cdots \lor t\_{n-2}$ ("carry"). This lets you compute the carry into the most significant bit in constant-depth and $O(n)$ gates. That's all you need for the results of the comparison (you don't need to compute the value of the other bits of the sum). The reason this requires fewer gates than a full addition or full subtraction is that we only need the carry into the most significant bit, not all the carry bits.

Double-check my reasoning -- I could have gone awry somewhere.
> 2 votes

---
Tags: lower-bounds, circuits, digital-circuits
---


# Question
Title: Why is constant always dropped from big O analysis?
Suppose I have an algorithm that has a performance of $O(n + 2)$. Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is $O(n)$.

However, say another algorithm has a performance of $O(n^2/2)$. Here if n gets really large then $n^2/2$ is exactly half of $n^2$, which is not significantly smaller than $n^2$. So why we drop 1/2 from $O(n^2/2)$ and it becomes $O(n^2)$?

# Answer
Big-O notation only describes the growth rate of algorithms in terms of mathematical function, rather than the actual running time of algorithms on some machine. As growth rate of function $f(n)=n^2$ is same as the growth rate of the function $g(n)=n^2/2$, we can say f(n) and g(n) both belongs to the same complexity set. See How:

Mathematically, Let $f(x)$ and $g(x)$ be positive for $x$ sufficiently large. We say that $f$ and $g$ grow at the same rate as $x$ tends to infinity, if

$\qquad\displaystyle \lim\_{x \to \infty} \frac{f(x)}{g(x)} = M$

for some $M \in \mathbb{R} -\\{0\\}$.

Now let $f(x)=x^2$ and $g(x)=x^2/2$, then $\lim\_{x \to \infty} f(x)/g(x)=2$. Thus $x^2$ and $x^2/2 $ both have same growth rate and we can say $O(x^2/2)=O(x^2)$.
> 1 votes

# Answer
When we evaluate complexity of algorithms, we count the number of computation steps, or of memory locations. But these costs are in arbitrary units. For example we have no idea how long it takes on computer X to actually execute one step of the algorithm. If you double the computer speed, you divide the time taken by 2, independently of the complexity formula, of the big-O complexity.

Hence this complexity is meaningful only up to a constant.

Hence, the 1/2 factor you mention is irrelevant. It is just the same as changing the computer, or changing the time unit. If you count in hours rather than seconds, you can get a whooping improvement factor of 3600. But you wait just as long to get the answer.

Here I did not mention that since it is supposed to be an asymptotic estimate, we first remove all that is asymptotically negligible

Another useful aspect of this definition of big-O is that you can ignore in the analysis the fact that some computations steps are more expensive than others. As long as there is a bound to the cost ratio between steps, they can simply be all considered costing the same. This can impact the total time only by a constant factor. It does make complexity analysis simpler.
> 7 votes

# Answer
Take a look at linear speedup theorem.

Basically, it says, that for every Turing machine $M\_1$ operating in time $f(n)$, and for every constant $0\<c\leq 1$, you can always make a Turing machine $M\_2$ solving the same problem in time $f(n) \cdot c + n + 2$. It's because of the fact, that each Turing machine can have a different work alphabet, set of states and transition relation. Each letter in $M\_2$'s work alphabet can correspond to a fixed number (roughly $1/c$) of letters in $M\_1$'s work alphabet. Compressing states and transitions in the same way results in a Turing machine $M\_2$ that is faster by a fixed constant (after you pay the linear time to rewrite the input).

In result, you can manipulate the constant in complexity function (both time and space) as needed.

And remember, that the extra $n + 2$ term is not *that* important, since people don't care about algorithms that give you an answer before they read the whole input.
> 4 votes

# Answer
Let $f(n)=\cal{O}(n^2/2)$. By definition this means there are constants $c\>0$ and $n\_0$ such that for all $n \geq n\_0$ we have $f(n) \leq c (n^2/2)$.

So $f(n) \leq c/2 \cdot n^2 = c' \cdot n^2$, where $c'=c/2$.

So there is a constant $c'\>0$ and $n\_0$ such that for all $n\geq n\_0$

$f(n) \leq c' \cdot n^2$.

This means $f(n) = \cal{O}(n^2)$.
> 0 votes

---
Tags: terminology, algorithm-analysis, asymptotics, landau-notation
---