# Question
Title: Why isn't TQBF part of the polynomial hierarchy?
TQBF consists of alternating quantifiers, so does $\Sigma^2\_n$ for fixed $n$. So given a formula in TQBF, shouldn't there be a level of the polynomial hierarchy that solves it?

I think this is incorrect because TQBF consists of any number of quantifiers, but each level in the PH has fixed number of quantifiers, so there's no level of the PH that can solve TQBF. Does it have to do with the fact that the number of quantifiers is part of the input in TQBF, whereas in PH only the formula is the input?

So this could also be worded as, if there exists a PH-complete problem, does TQBF reduce to that problem?

# Answer
What you're missing is the distinction between QBF and 2QBF.

It's an open problem whether TQBF is contained in any level of the polynomial hierarchy, but it'd be reasonable to expect that TQBF is probably not contained in any level of the polynomial hierarchy.

TQBF is PSPACE-complete. Also, if PSPACE = PH, then the polynomial hierarchy collapses. Thus, if TQBF is in some level of the polynomial hierarchy, then so is all of PSPACE, and thus the polynomial hiearchy collapses.

It is conjectured that the polynomial hierachy does not collapse. However, this is merely a conjecture, analogous to the conjecture that P $\ne$ NP; whether or not this is true is an open problem.

> TQBF consists of alternating quantifiers, so does $\Sigma^2\_n$ for fixed $n$.

Giraffes consist of atoms. So do light bulbs. Therefore, every giraffe is also a light bulb.

What's wrong with that reasoning? The same thing that's wrong with your reasoning.

Check your definitions. $\Sigma\_n^2$ allows formulas that contain only *two* alternations of quantifiers, i.e., 2QBF. QBF allows an unlimited number of alternations of quantifiers. 2QBF is complete for $\Sigma\_n^2$; QBF is complete for PSPACE.
> 2 votes

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


# Question
Title: If modern computers aren't actually Turing-complete, does that mean that it is possible to determine if a program run on such a computer halts?
The halting problem says that it is impossible to create a general algorithm which can for all inputs and programs determine whether they halt. However, this assumes that the programs and/or the things running them are Turing-complete.

Since all computers have a finite amount of memory and are therefor *not* Turing-complete, does that mean that the halting problem does not apply to a program run on a machine with finite memory?

# Answer
> 6 votes
You can take a look at: https://en.wikipedia.org/wiki/Halting\_problem#Common\_pitfalls

One can realize that a program is not halting by seing that it's repeating its behavior.
"A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state"

It also says that even computers are finite state machine, it's more useful to model them as infinite state machines, just because the number of states it's huge.
"Minsky warns us, however, that machines such as computers with e.g., a million small parts, each with two states, will have at least $2^{1,000,000}$ possible states"

# Answer
> 5 votes
If you have a particular machine with a finite state space, you can determine whether a program run by that machine halts by watching it until it either halts or the state of the machine is repeated. This isn't very practical (your halting-checker needs to have vastly more memory than the machine being checked, in order to remember states), but it is decidable.

Of course, that's for a very particular finite state machine implementation running your program. Execution of a program can be abstractly Turing-complete (can theoretically access unbounded memory) even if the actual machine it's practically run on doesn't have unbounded memory. So even if you could check that a program halts on a particular machine (such as by crashing due to insufficient resources), that doesn't necessarily tell you whether the equivalent program would have halted on a different machine with more memory.

# Answer
> 5 votes
Indeed, the theoretical undecidability of the halting problem does not apply to any concrete computer with finite memory. That's a finite system, so for any program, it's mathematically possible to determine whether it halts on a particular computer.

The thing is, this mathematical property is useless in practice.

The main reason for that is that while it's *mathematically* possible to determine whether a program halts on a computer with finite memory, it may not be *physically* possible. A computer with $n$ bits of memory has $2^n$ states. The naive way to determine whether a program halts on a finite-state computer is to run it and see if the states repeats before the program halts. But the number of states is so large than this is physically impossible even for relatively small values of $n$. Not only is there not enough time in a human life, there isn't enough energy to do it! Landauer's principle gives a lower limit for the amount of energy consumed by a computer (with any technology that we currently recognize as a computer), and the Solar system only has about enough energy for a little over 200 bits (see Amount of simple operations that is safely out of reach for all humanity?). That's billions of time fewer bits than a typical PC. The whole universe has enough energy, but if you're working on that scale you're probably going to want to analyze a bigger computer, and the ratio between doing and analyzing gets exponentially worse.

In addition, even if you lucked out and found some tricks to analyze the program faster (which isn't always possible — it would effectively mean that you could systematically compress a program — but it might be possible for “interesting” programs), the analysis would only tell you that the program halts, or doesn't halt, on a computer with $n$ bits of memory. It wouldn't tell you whether the program halts on a computer with $n+1$ bits of memory.

In some applications (e.g. a heart monitor or a brake controller), it's very important to know not only that a program will run in a certain fixed amount of memory, but also that it will run in a certain amount of time. For this kind of situation, the halting problem isn't relevant. There is a cost to doing such precise analysis: you need to keep the programs simple enough to stay very, very, very, very far from the theoretical maximum complexity.

In other applications (e.g. a server operating system or a compiler), the exact amount of memory and the exact time are not so important, but we want to be able to analyze complex programs. In this model, removing the time taken and the memory consumption from the analysis makes things a lot easier. It's a well-known phenomenon in mathematics that it's often easier to reason in infinite space than in large finite space, because in large finite space you have to constantly check whether you're bumping into some limit. Here the halting problem corresponds to a useful question to ask in practice.

# Answer
> -1 votes
I agree with the (unanimous) preceding answers regarding finite-memory machines. But I don't see how to apply that argument to the following situation.

Suppose you claim to have a C-language (or any Turing complete language) function

**int halts(char \*filename)**

which reads another C-language program contained in **filename** and returns **1** if that program eventually halts, returns **0** if not, and just for completeness (i.e., so that **halts()** is a total function) returns **-1** if the contents of **filename** don't comprise a valid program.

Now, write the following little program and store it in file **doIhalt.c**

```
int main(int argc, char *argv[]) {
  int halts();
  while ( halts("doIhalt.c") == 1 ) continue;
  exit; }

```

Thus, if **halts()** claims **doIhalt.c** halts, then it explicitly continues forever; whereas, vice versa, it immediately exits if **halts()** claims it doesn't halt. So, this is all on a finite-memory machine (assuming the **halts()** function is finitely implemented), but I don't see how to decide whether or not **doIhalt.c** halts.

---
Tags: computability, halting-problem
---


# Question
Title: Solving second-order ODEs with Taylor series approximation of second derivative and linear algebra
I was told about an algorithm to solve ODEs which I thought was very clever. I am sure its not something new. It works by discarding the $\mathcal{O}(h^2)$-term from the usual formula for computing the second derivative:

$$f''\_i = \frac{f\_{i-1} + f\_{i+1} - 2f\_{i}}{h^2} + \mathcal{O}(h^2), \qquad i = 0,1,2,\cdots,N$$

one can rewrite the equations for the derivatives for all $i$, as a set of linear equations, then use smart Gauss elimination from linear algebra to find expression for $f$ with exactly $5N$ floating point operations.

(1) Does this method already have a name?

(2) Should I be excited about this algorithm? Is this a particularly good method? Or are there other very different algorithms for solving ODEs which are much better?

# Answer
This is essentially the (implicit) Finite Difference Method. There are different variations based on the discretization (implicit, explicit, Crank-Nicolson, leap-frog, etc). Some better than others. For the implicit approach, you can use Thomas Algorithm (modified Gaussian elimination) to solve the tridiagonal system. But you can also use Cyclic Reduction (or one of its variations) which allows you to solve the system in parallel on GPUs and clusters. Much much larger solvers rely on Krylov subspace methods. There are other ODE/PDE solves like Method of Lines, Finite Element Method, and many many others that you'd encounter in a good text on Numerical Analysis (e.g., Kincaid, Cheney).
> 3 votes

# Answer
What you have there is the central difference approximation to the second derivative. The Wikipedia article on finite differences explains this pretty well.

Of course, this isn't a *method* as such; that depends on the exact problem being solved. If this were an initial value problem, then a simple rearrangement of this equation is typically known as Störmer–Verlet integration (or just Verlet integration depending on whom you ask).

If it was a bounding-value problem, then this discretisation of the derivative gives you a tridiagonal system, and you don't have a complete "method" until you have a method to solve it. A small modification of Gaussian elimination is quite efficient on matrices of this form.

As to competitors... that's a very long discussion. Any introductory textbook on numerical analysis should give you a good start.
> 3 votes

---
Tags: algorithms, discrete-mathematics, numerical-algorithms
---


# Question
Title: The complexity of BDD Synchronous Composition
As shown in Byrant's original paper, the time complexity of (single-variable) composition algorithm is cubic, and it is a tight upper bound. My question is about synchronous composition, written as $$f' = f(x\_{1},\dots,x\_{n})|\_{x\_1=g\_1, \dots, x\_n=g\_n}$$ where you replace all variables of $f$ synchronously with other Boolean functions $G$ over $X$.

However, I couldn't find an explicit reference mentioning time and space complexity of synchronous composition for BDDs. Is anyone of you aware of such results?

# Answer
I'm not aware of such a result in any paper, but that may be because it is relatively clear that this operation is non-polynomial.

And here is why. Assume that we have a *satisfiability problem* with $n$ variables and $c$ clauses. We allocate variables $v\_1, \ldots, v\_n$ and $v'\_1, \ldots, v'\_c$ in the BDD manager, build a BDD

$$B = \bigwedge\_{i \in \\{1, \ldots, c\\}} v'\_i$$

and also BDDs $x\_1, \ldots, x\_c$ that encode the clauses over $v\_1, \ldots, v\_n$. Note that all BDDs are of size $O(c)$ or $O(n)$, which is even independent of the variable ordering.

Now computing

$$C = B\[x\_1/v'\_1,x\_2/v'\_2, \ldots, x\_c/x'\_c\]$$

gives us a BDD that represents the set of all solutions to the SAT problem (where \[...\] is the application of the synchronous composition operator). If we could compute $C$ in time polynomial in the size of the SAT instance, that would give us a polynomial time algorithm for SAT. Even more, with $C$, we can count the number of solutions, which lies in a higher complexity class that finding them. Also, making use of a fixed variable ordering of the BDD, the argument can be extended to talk about the QBF problem, which is PSPACE complete.

Obviously, this does not answer your question to 100%. But in the light of this line of reasoning, I would find it surprising if the algorithm actually implemented in BDD libraries was polynomial-space (or even polynomial time).
> 1 votes

---
Tags: complexity-theory, reference-request, time-complexity, space-complexity, bdd
---


title: What defines a subproblem?

text:
# Question
Title: What defines a subproblem?
In algorithm analysis what exactly defines a subproblem?

I know that one of the optimality conditions for greedy algorithms is that all subproblems of the solution are also optimal, but to me this begs the question. Are subproblems defined relative to a data set, a problem on that data set, or a solution to that problem?

As an example, a shortest path algorithm on a connected graph with vertices {a,b,c,d,e} for a path from a to e may return {(a,b),(b,c),(c,d),(d,e)}, and the subproblems here to me are every path from an earlier vertex in the list to a later vertex in the list, implying that you have subproblems relative to a solution.

An example that confuses me, however, is dealing with sequence alignment on strings. Given an optimal alignment for two sequences, what are the subproblems? Is it the alignment of any partition of the two strings? Because the answer to an alignment problem can actually return different strings.

For example, if we're aligning \["AT","CAT"\] we should get \["\_AT","CAT"\]

But for the 0th index here it doesn't make sense to say that \["\_","C"\] is a subproblem, or that \["A","C"\] is a subproblem, because they're both trivial (alignment of two singletons can never be suboptimal), and \["A","C"\] is never actually aligned/compared in the result.

# Answer
> 4 votes
There is no formal definition. A subproblem is just a (usually smaller!) problem that you solve on the way to solving the problem you're really interested in.

---
Tags: algorithms, terminology
---


# Question
Title: Check for balanced parentheses in an expression in log-space
Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”\[“,”\]” are correct in the expression. For example, the program should print true with begin-end pair of symbols indices for exp = “\[()\]{}{()()}” and false for exp = “\[(\])”.

The naive solution with a stack has O(n) time-complexity and O(n) space-complexity. Can we solve this problem in O(log(n)) space-complexity? In other words, can we parse Dyck languages in logarithmic space?

# Answer
> 7 votes
The Dyck language on any fixed number of symbols can be recognised by a marking automaton, which is a two-way finite automaton that can mark a fixed number of input tape squares. The automaton simply uses a different mark for each type of parenthesis. Since a marking automaton is easily implemented by a Turing machine with a fixed number of logarithmic-sized regions of the worktape forming pointers into the input, Dyck languages can be parsed in logspace.

* R. W. Ritchie and F. N. Springsteel, *Language Recognition by Marking Automata*, Information and Control **20**, 313–330, 1972. doi:10.1016/S0019-9958(72)90205-7

---
Tags: complexity-theory, context-free, space-complexity, parsers
---


# Question
Title: what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length?
I'm working on an algorithm and I'm trying to figure out its time complexity given the operations it takes to complete a input set of specific length, I have been testing the algorithm with varying input lengths.

The results shows that every time I double the input length, it takes 4 times more operations than before to complete:

* 20 items = 1M (M=million)
* 40 items = 4M
* 80 items = 16M
* 160 items = 64M
* 320 items = 256M
* 640 items = 1024M

What is the time complexity/running time that fits better with the above results?

# Answer
> 5 votes
Recurrent equation: $$T(n) = 4 \cdot T(\frac{n}{2})$$ $$T(1) = O(1)$$ Its solution: $$T(n) = \Theta(n^2)$$

# Answer
> 3 votes
Unless you are promised that this pattern continues ad infinitum, you can not conclude anything. Asymptotic properties can not be inferred from finite samples, ever.

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


# Question
Title: Space complexity of string indices: O(1) or O(log|S|)?
Say you have a string `S` and wish to store indices of it, e.g. letter at index 3 of "toast" is 'a'. Seems that people generally consider an index as taking `O(1)` space to store\*. But doesn't it take `O(log(|S|))` space?

If we use binary bits...

* length 4 string =\> index must be at least 2 bits
* length 8 string =\> index must be at least 3 bits
* length n string =\> index must be at least `log(n)` bits

\*An example of where I'm seeing `O(1)` suggested: educational sources state that a suffix tree has `O(|S|)` space complexity, where `S` is the input string, because there are `O(|S|)` nodes in the tree, and each node is just an index in the input string. This implies that each index takes `O(1)` space, but this seems untrue to me. Seems like the tree takes `O(|S| log(|S|))` space.

\*More examples: Many basic data structures (hash tables, BSTs, etc) use memory pointers (equivalent to string indices), and everyone considers these pointers fixed-size.

# Answer
These are correct (unless you explicitly specify a non-standard model of computing):

* $O(1)$ space,
* $O(1)$ words of space,
* $O(\log|S|)$ bits of space.
> 5 votes

# Answer
Depends on which model you are interested in.

On RAMs with the *uniform* or *unit* cost model, (not too large) numbers take constant space to store, and constant time to work with.

On RAMs with the *logarithmic* cost model and TMs, they take logarithmic space.
> 1 votes

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


# Question
Title: Can a $k$-ary relation have polymorphisms of arity greater than $k$?
To quote Hubie Chen's A Rendezvous of Logic, Complexity, and Algebra (2009) on constraint satisfaction and complexity,

> An operation $f : D^m \to D$ is a polymorphism of a relation $R \subseteq D^k$ if, for any choice of $m$ tuples $(t\_{11}, ... , t\_{1k}), ... , (t\_{m1}, ... , t\_{mk})$ from $R$, it holds that the tuple obtained from these $m$ tuples by applying $f$ coordinate-wise, $( f (t\_{11}, ... , t\_{m1}), ... , f (t\_{1k}, ... , t\_{mk}))$, is in $R$.

Two examples follow, but neither answers this question. Let's say that there's a relation $R$ and function $f$ such that $m \> k$. Is $f$ a polymorphism of $R$?

Concrete example: Assuming an $\wedge$ relation $\\{ (1,1) \\}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

# Answer
> 2 votes
> Let's say that there's a \[$k$-ary\] relation $R$ and \[$m$-ary\] function $f$ such that $m\>k$. Is $f$ a polymorphism of $R$?

Maybe, maybe not: it depends on the function and the relation. A given $k$-ary relation may have polymorphisms of arity arity less than, equal to, and/or greater than $k$. In fact, every relation has polymorphisms of all arities. For example, the ($1$-ary) identity function is a polymorphism of every relation, as are the projection functions $f\_\ell(x\_1, \dots, x\_m) = x\_\ell$ for all $1\leq \ell\leq m$. (Exercise: check these examples.) Notice that the identity function is just the case $\ell=m=1$.

> Concrete example: Assuming an $\wedge$ relation $\\{ (1,1) \\}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

Check the definition! $f$ is a polymorphism of $R\_\land = \\{(1,1)\\}$ if, and only if, for all $(x\_1,x\_2),(y\_1,y\_2),(z\_1,z\_2)\in R\_\land$, we have $(f(x\_1,y\_1,z\_1),f(x\_2,y\_2,z\_2))\in R\_\land$. Well, the only tuple in $R\_\land$ is $(1,1)$, so we only care about the case $x\_1=y\_1=z\_1=x\_2=y\_2=z\_2=1$. And we see that $f(1,1,1)=1$, so $(f(1,1,1),f(1,1,1))\in R\_\land$, so $f$ is, indeed, a polymorphism of $R\_\land$. Further, by exactly the same argument, *any* function such that $f(1, \dots, 1) = 1$ is a polymorphism of $R\_\land$.

The polymorphism property is often represented as a table: given a $k$-ary relation $R$ and an $m$-ary function $f$, we can write

$$\begin{matrix} (t\_{1,1} & t\_{1,2} & \cdots & t\_{1,k}) & \in R\\ (t\_{2,1} & t\_{2,2} & \cdots & t\_{2,k}) & \in R\\ \vdots & \vdots & \ddots & \vdots & \\ (t\_{m,1} & t\_{m,2} & \cdots & t\_{m,k}) & \in R\\ \hline (f(t\_{1,1}, \dots, t\_{m,1}) & f(t\_{1,2}, \dots, t\_{m,2}) &\cdots & f(t\_{1,k}, \dots, t\_{m,k})) &\in R \end{matrix}$$

The meaning is that we require that, whenever the tuples above the line are in $R$, the tuple below the line must also be in $R$. Notice that nothing in the structure of the table requires any relation between $k$ and $m$: the property could hold (or not hold) for a relation of any arity and a function of any arity. It's just required that, whenever we write a collection of tuples in $R$ and "apply $f$ to each column", the resulting tuple is always still in $R$.

---
Tags: relational-algebra, constraint-satisfaction, polymorphisms
---


# Question
Title: Extract Tree from multi-edge undirected graph
I have the following multi-edge, undirected graph.

I would like to extract the following tree from it, if I start from the node $A$.

Do you know of any algorithm that I can use to achieve that ?

---

The problem I am trying to solve is the following.

The first graph represent different relational tables I want to join. Each edge $e\_i$ represents one join between two tables (two tables could be joined on different fields, for example).

From that graph, I need to create the tree depicted in the second figure. That tree is then used for executing the joins.

Thanks

# Answer
> 1 votes
The problem is under-specified; nonetheless, I will try to help assuming that you are looking for the graph traversal tree.

To obtain such a tree, you can use a graph traversal algorithm such as breadth-first search. You can find a nice implementation of this algorithm in The Algorithm Design Manual by Steven Skiena.

Note that you need to adapt an important aspect of the algorithm:

* Do not set a node as *discovered* unless the node has been visited from all of its incoming edges. Without this adaptation, each node will only be visited once, and, therefore, the behaviour of the algorithm will be the same as if multi-edges did not exist.

You will also need a data structure to store the tree of interest. In Skiena's implementation, this data structure is an array that is called `parent`: if node `i` is discovered from node `j`, then `parent[i] = j`.

> The vertex that discovered vertex *i* is defined as **parent\[i\]**. Every vertex is discovered during the course of traversal, so, except for the root, every node has a parent. The parent relation defines a tree of discovery with the initial search node as the root of the tree.
>
> *Steven Skiena - The Algorithm Design Manual*

However, note that you will need a slightly more complex data structure to support duplicated nodes.

# Answer
> -1 votes
I have some solution, not sure this is the best:

* I consider a multiedge as single edge, and I keep track where they appear. This way I have a simple graph.
* Starting from the root node, I traverse the graph in order to create a tree
* for each of the multiedges, I clone the sub-tree add it to the parent. This needs to be done bottom-up (from the leaves to the root).

---
Tags: algorithms, graphs, trees
---


# Question
Title: Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays?
I've just started reading about theory of distributed systems and am a bit confused. There seem to be two ways of defining a synchronous distributed system and I'm not sure whether they are equivalent.

Lynch, in her book Distributed Algorithms (p. 5) writes

> The synchronous model: This is the simplest model to describe, to program, and to reason about. We assume that components take steps simultaneously, that is, that execution proceeds in synchronous rounds.

Several other sources, in contrast, define the synchronous model in terms of known upper bounds for computation and communication delays. For instance, Cachin et al. in their book Introduction to Reliable and Secure Distributed Programming (pp. 45-46) write

> \[...\] a synchronous system comes down to assuming the following properties:
>
> Synchronous computation. There is a known upper bound on processing delays. That is, the time taken by any process to execute a step is always less than this bound. \[...\]
>
> Synchronous communication. There is a known upper bound on message transmission delays. That is, the time period between the instant at which a message is sent and the instant at which the message is delivered by the destination process is smaller than this bound.

Even Lynch herself, in a paper she cowrote with Dwork and Stockmeyer (Consensus in the Presence of Partial Synchrony) also uses a definition similar to the one by Cachin et al.:

> \[...\] it might be assumed that there is a fixed upper bound $\Delta$ on the time for messages to be delivered (communication is synchronous) and a fixed upper bound $\Phi$ on the rate at which one processor’s clock can run faster than another’s (processors are synchronous), and that these bounds are known a priori and can be "built into" the protocol.

Are these synchronous models equivalent? For instance, is an impossibility result in one also an impossibility result in the other, and vice versa? And is the minimum number of nodes necessary to tolerate a given failure (e.g., byzantine or crash) the same, whether we define synchronous to mean that processes proceed in synchronized steps or whether we define it as meaning that transmission and computation delays are upper bounded and known?

# Answer
All of these are, generally speaking, called "synchronous models", they are pretty similar to each other, and especially in the context of fault-tolerant algorithms they are very different from "asynchronous models".

However, please note that there is no such thing as *the* synchronous model. Even if you define a message-passing model in which all nodes execution proceeds in synchronous rounds and all nodes start simultaneously, this does not yet completely define the model of computing. To have a well-defined model of distributed computing, you will need to specify, e.g., the following aspects:

* assumptions on the underlying network topology (complete network? path? cycle? grid? bounded-degree graph? arbitrary graph?)
* what kind of local information the nodes have in the beginning (unique identifiers? an upper bound on the network size?)
* what is the communication model (maximum message size? can you send different messages to each neighbour in the same round or are you limited to e.g. broadcast operations? can you receive messages from different neighbours in the same round or do you have collisions? how can you address your neighbours?)
* what kind of computers you have as your nodes (finite state machines? Turing machines? arbitrary functions? any limitations on time or space used per round? any limitations on space used between rounds? can you use randomness?).

These aspects can be *much more important* than the specific definitions of "synchrony", especially if you are interested in computability.

But let us put these issues aside, let us assume we have already precisely defined some synchronous model of computing (and let us also assume that it is a fairly strong model, e.g., we have unique identifiers and unlimited local computation). Let us now try to see whether the precise definition of "synchrony" would make any difference.

If you only care about *computability*, the precise definition of "synchrony" is not important. Also, if you are only interested in the *number of communication rounds* needed to solve a problem (and you define a "communication round" appropriately so that it makes sense also in the bounded-delay model), the models are also equivalent up to constant factors. In essence, you can simply use the alpha synchroniser: all nodes count rounds from 1, all messages include round counters, and each node proceeds to round $i+1$ once it has received all messages from round $i$ (and you use timeouts to detect nodes that have crashed).

Things get more complicated if you also care about e.g. the *total number of bits that you need to transmit*. In essence, in the "strict" synchronous model you can easily use *silence to send information* (e.g., be silent for $x$ rounds and then send a 1-bit message ≈ send number $x$). Here is a simple example of a problem that can be solved this way:

* the underlying graph is a path and all nodes need to determine how far they are from the nearest endpoint.

If all nodes start simultaneously and computation proceeds in synchronous rounds, it is sufficient to propagate a 1-bit token from the endpoints towards the middle. All nodes can locally count how many rounds it takes before they receive the token. In total, in a path of length $n$, you will send approximately $n$ messages, each of them containing just one bit.

However, if you have bounded delays, it gets pretty tricky to solve this problem with $O(n)$ 1-bit messages. You can still use periods of silence to send information, but you will need to waste a lot of time to do that (a naive solution has an *exponential* time complexity).
> 4 votes

---
Tags: computation-models, distributed-systems
---


# Question
Title: Applying Machine learning in biological data
I am trying to solve the following question: Given a text file containing a bunch of biological information, find out the one gene which is {up/down}regulated. Now, for this I have many such (60K) files and have annotated some (1000) of them as to which gene is {up/down}regulated.

## Conditions

* Many sentences in the file have some gene name mention and some of them also have neighboring text that can help one decide if this is indeed the gene being modulated.
* Some files also have NO gene modulated. But these still have gene mentions.

Given this, I wanted to ask (having absolutely no background in ML), what sequence learning algorithm/tool do I use that can take in my annotated (training) data (after probably converting the text to vectors somehow!) and can build a good model on which I can then test more files?

## Example data

> Title: Assessment of Thermotolerance in preshocked hsp70(-/-) and (+/+) cells
>
> Organism: Mus musculus
>
> Experiment type: Expression profiling by array
>
> Summary: From preliminary experiments, HSP70 deficient MEF cells display moderate thermotolerance to a severe heatshock of 45.5 degrees after a mild preshock at 43 degrees, even in the absence of hsp70 protein. We would like to determine which genes in these cells are being activated to account for this thermotolerance. AQP has also been reported to be important.
>
> Keywords: thermal stress, heat shock response, knockout, cell culture, hsp70
>
> Overall design: Two cell lines are analyzed - hsp70 knockout and hsp70 rescue cells. 6 microarrays from the (-/-)knockout cells are analyzed (3 Pretreated vs 3 unheated controls). For the (+/+) rescue cells, 4 microarrays are used (2 pretreated and 2 unheated controls). Cells were plated at 3k/well in a 96 well plate, covered with a gas permeable sealer and heat shocked at 43degrees for 30 minutes at the 20 hr time point. The RNA was harvested at 3hrs after heat treatment

Here my *main* gene is `hsp70` and it is `down-regulated` (deducible from `hsp(-/-)` or `HSP70 deficient`). Many other gene names are also there like `AQP`. There could be another file with no gene modified at all. In fact, more files have no actual gene modulation than those who do, and all contain gene name mentions.

Any idea would be great!!

# Answer
> 2 votes
A simple starting point would be to apply a bag-of-words feature vector and try using a naive Bayes or logistic regression classifier. You'll probably want to apply stemming and lemmatization and remove stop words.

Going based on this one example, determining which gene is regulated looks like it might be plausibly feasible, but determining whether it is up- or down-regulated might be pretty tough, especially given the limited training set you have. Of course, it's hard to know without seeing more examples and without some domain knowledge in biology.

There are lots of techniques in the NLP literature, and probably your best bet is to start by reading up on standard NLP methods and start trying some of them, and see if that raises a more narrowly targeted question. Machine learning often requires significant experimentation (try a bunch of things). It's also helpful to know standard techniques so you can use your domain knowledge of these documents to help you brainstorm possible features.

---
Tags: machine-learning, natural-language-processing
---


# Question
Title: Complexity class for concurrent algorithms
We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in a similar way?

Motivation:

A sequential algorithm may be O(n7) but its parallel implementation might make it O(1) so what is the motivation and tradeoff between spending time to design lower complexity algorithms then simply paralyzing it to achieve an even better performance? How this fact could be incorporated in the complexity theory notations?

Note:

Writing a parallel version is also a challenge but many times its a low hanging fruit which can be quickly solved without much creativity.

# Answer
Parallel complexity uses the same Landau notation but a different machine model, usually the PRAM which allows polynomially many processors (in the input size). This gives rise to complexity classes like NC.

If you are into *algorithms* outside of massively-parallel settings, this is all quite useless: the existence of PRAM algorithms does not tell you anything about algorithms on "real" computers, i.e. such with finitely many processors.
> 1 votes

---
Tags: complexity-theory, asymptotics, parallel-computing, landau-notation
---


# Question
Title: Meaning of the constants that appear in the Master Theorem
The general formula for time complexity is $T(n) = aT(n/c) + bn^k$.

* If $a\> c^k$, the complexity is $O(n^{\log\_c a})$.
* If $a = c^k$, it is $O(n^k \log n)$.
* If $a \< c^k$, it is $O(n^k)$.

$a$ is the amount of times the recursive function is called, but what do $b$, $c$, and $k$ represent?

# Answer
That is *not* the general formula for time complexity. There is no "general formula for time complexity", any more than there is a "general formula for the answer."

Rather, the formula you give is a recurrence relation that can be used to compute the running time of certain divide-and-conquer–style recursive algorithms. Specifically, it corresponds to a recursive function which, when given an input of size $n$, makes $a$ recursive calls, each on inputs of size $n/c$. If you pretended that the recursive calls were "free" (i.e., that they returned their answer in one computation step), then the algorithm would take $bn^k$ steps.
> 4 votes

# Answer
The Master theorem applies to recurrences of a certain form; in algorithm analysis, usually such for running-time functions of *divide & conquer* algorithms. If you look at some examples, you'll note that the common scheme is that

1. the input is divided into parts of size $n/c \pm 1$,
2. the algorithm is executed recursively on $a$ of these parts, and
3. the results of the recursive calls are then combined into the final result.

Now, steps 1 and 3 take some time, which the authors of that "general formula" of yours (which is anything but) assume to be of the form $bn^k$ (they probably *mean* $\Theta(n^k)$, or even $O(n^k)$, but simplify to this explicit function so the calculations work out more neatly).

See here for a longer explanation of the Master theorem with applications. There are some other questions on the Master theorem you may want to read through.
> 2 votes

# Answer
I think you must mean solving recurrences of the form *T(n) = aT(n/b) + f(n)*.

From the relations that you have written I understand that you must be trying to learn the Master Method for solving recurrences. This is used where a divide and conquer strategy is used by the algorithm to solve problems. The D&C strategy divides a given problem into specific parts in order to solve it effectively.

Here *a* implies the number of parts a single problem is divided into.

*(n/b)* is the size of each sub-problem and

*f(n)* is the cost of solving(combining and splitting) each sub problem.

More details of the master method can be understood from here as suggested earlier by Raphael
> -1 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation, master-theorem
---


# Question
Title: Does the amount of symbols a turing machine has affect what computations it can perform?
Do additonal symbols on a turing machine actually change what is computationally possible on a machine, or do they just make them easier to work with? For example is there anything a 3 symbol turing machine could compute that a 2 symbol turing machine could not? (Assuming each machine can have any number of states).

# Answer
Hint: can you express more integers by writing them in a bigger base?

I'll go with the definition where the blank is counted as a symbol. A Turing machine must have at least one non-blank symbol, i.e. at least two symbols. With 0 symbols there's no way to build a tape, and with only the blank symbol there's a single possible tape so the machine is effectively a finite automaton.

Any $n$-symbol Turing machine can be translated to a Turing machine with the symbols $\\{0,1\\}$ where $0$ is the blank symbol. Let $k$ be an integer such as $2^k \ge n$, and number the symbols from $0$ to $n-1$, with the blank symbol numbered $0$. Translate the tape by mapping each symbol to the sequence of $k$ symbols that is the representation of its number in base $2$.

The state set increases. For each original state $q$, we define several types of states in the new machine:

* Forward read states $(\mathsf{R},q,i,x)$ where $0 \le i \le k-2$ and $x \le 2^i$: read the bits that represent one original input symbol, remembering the position $i$ and the partial accumulated number. These states have a right transition to either $(\mathsf{R},q,i+1,2x)$ or $(\mathsf{R},q,i+1,2x+1)$ depending on the symbol read from the new tape.
* Decision states $(\mathsf{R},q,k-1,x)$: if there is a transition $\delta(q,x) = (q',x',d)$ in the original machine, then transition to a write state $(\mathsf{W},q',d,k-1,x')$. If the state $q$ is final in the original machine, this state is final in the new machine.
* Write states $(\mathsf{W},q',d,i,x')$ where $1 \le i \le k-1$ and $x' \le 2^i$: write the low-order bit of $x'$ to the tape and move left to $(\mathsf{W},q',d,i-1,\lfloor x'/2 \rfloor)$.
* Last-bit write states $(\mathsf{W},q',d,0,x')$ where $x' \in \\{0,1\\}$: write $x'$ to the tape, and move to a fast-forward state or a fast-backward state depending on $d$.
* Fast-forward and fast-backward states $(\mathsf{F},q',d,i)$ where $0 \le i \le k-1$: keep moving in the same direction and decrement $i$ until it reaches $0$, at which point, switch to the corresponding forward read state. These states are used to either skip forward to the beginning of the part of the tape that represents the next original symbol after a right transition in the original tape, or to skip backward to the beginning of the part of the tape that represents the previous original symbol after a left transition in the original tape.

In summary, we make three passes over each symbol: one to read it, one to write the new symbol, and one to reposition the tape.

The details are tedious but not difficult.
> 2 votes

---
Tags: turing-machines, computation-models
---


title: Error correcting permutation code

text:
# Question
Title: Error correcting permutation code
Let's say you have $n$ symbols. You can encode a $\log\_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a reference).

Let's say we are encoding a message with $k\<\log\_2(n!)$ bits. It is possible to add error correction. One way is to simply add any old error correction scheme to the string before applying the permutation code. I'm wondering if there is a way that is optimal for permutation codes.

In particular, is there some way of doing a permutation coding that is resistant to transpositions (in terms of error detection and correction)? I want something that will tolerate up to $t$ transpositions of *adjacent* symbols.

# Answer
> 2 votes
The first reference seems to be Rank permutation group codes based on Kendall's correlation statistic by Chadwick and Kurz; your notion of distance is known as Kendall's tau distance. A more modern reference is Codes in Permutations and Error Correction for Rank Modulation by Alexander Barg and Arya Mazumdar

---
Tags: coding-theory, permutations, encoding-scheme, error-correcting-codes
---


# Question
Title: Do problems in P have a minimum number of YES and NO instances?
If a decision problem A belongs to the polynomial complexity class P, must there be at least one YES instance and one NO instance of the problem? I know that in the definition of a Turing machine an accept state and separate reject state are defined but I'm not sure if that applies to this case. Is it maybe possible to have only YES instances or only NO instances?

Thanks very much in advance.

# Answer
> 8 votes
If a problem has only "YES" instances (resp. only "NO" instances), then the associated *language*, which is our formalization of a "problem" contains every word in $\Sigma^\*$ (resp. no words), with $\Sigma$ being the underlying alphabet.

Both $\Sigma^\*$ and $\emptyset$ are regular languages, and in particular, are both in $P$.

So yes - there are trivial languages are in $P$.

In fact, this argument also works when there are finitely many YES or NO instances, since finite languages are regular, and also their complements are.

So for a language *not* to be in $P$ it must first of all have both infinitely many YES and infinitely many NO instances.

# Answer
> 3 votes
If a problem has only a finite number of YES instances or only a finite number of NO instances then it can be solved in constant time by checking whether an instance of the problem matches one of this finite number of instances.

A problem that cannot be solved in O (1) must have an infinite number of YES and an infinite number of NO instances. That doesn't apply to P, which contains constant time problems.

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


title: Is there a measure for connectedness?

text:
# Question
Title: Is there a measure for connectedness?
Is there a name for the "measure of connectedness", i.e. : $$\text{MoC} = \frac{d(G)}{|G|-1}$$ with domain of function $D\_\text{MoC} = \[0,1\]$, average degree of graph $d(G)$ and amount of nodes $|G|$? Meaning a quantitive measure for connectedness or meshedness of a graph? E.g. a complete graph would have a MoC of 1, while a graph without edges would have a MoC of 0.

# Answer
Your measure is known as the density of the graph, and is given by the formula $$ \frac{|E|}{\binom{|V|}{2}}, $$ where the graph is $G = (V,E)$.
> 4 votes

---
Tags: graphs, terminology
---


# Question
Title: What is the trick of "adding a huge number" for in the reduction from 3-Partition?
**Problem:** To prove the $\textsf{NP-Completeness}$ of the problem of *"Packing Squares (with different side length) into A Rectangle"*, $\textsf{3-Partition}$ is reduced to it, as shown in the following figure.

In the $\textsf{3-Partition}$ instance, there are $n$ elements $(a\_1, \cdots, a\_i, \cdots, a\_n)$. The target sum $t$ is $t = \frac{\sum a\_i}{n/3}$.

In the reduction, **$B$ is a huge (constant) number** and each $a\_i$ is represented by a $(B + a\_i) \times (B + a\_i)$ square. The blank in the rectangle will be filled by unit ($1 \times 1$) squares.

---

**Questions:** I don't quite understand the trick of "adding a huge number $B$" in the reduction. I guess it is used to force that any packing scheme will give a solution to $\textsf{3-Partition}$. But how?

> Question 1: What is the trick of "adding a huge number" for in the reduction from $\textsf{3-Partition}$? Specifically, why does this reduction work? Why is this trick necessary, i.e., why wouldn't the reduction work if we left out $B$ (set $B=0$)?

I tried to identify the flaw of the proof of "any packing gives a 3-partition" but could not get the key point.

Actually I have also seen other reductions from $\textsf{3-Partition}$ that also use this trick. So,

> Question 2: What is the general purpose of this trick of "adding a huge number" in the reductions from $\textsf{3-Partition}$ (*if there is*)?

---

**Note:** This problem is from the video lecture (from 01:15:15) by Prof. Erik Demaine. I should have first checked the original paper "Packing squares into a square". However, it is not accessible to me on the Internet. If you have a copy and would like to share, you can find my mailbox in my profile. Thanks in advance.

# Answer
The large $B$ is here to ensure that the squares follow the pattern shown in the figure.

In the part "there exists a packing $\Rightarrow$ there exists a 3-partition". You need to exhibit tripples of integers with sum $=t$. This is easy if the coding squares in the packing are arranged 3-by-3 as in the picture, but how do you know this is the case? For instance, with very slightly smaller blue squares, you could have two small squares side by side in the same column, and then you'd be in trouble.

One way to use the trick of the $B$ constant is to say that it is not possible to have any horizontal line crossing strictly more than $n/3$ squares (such a line has length $(B+t)\frac n3$, a square has size at least $B$, and $B \> t\frac n3$). So each horizontal line meets a 1st square, a 2nd square, etc., and then you can show (again using the large $B$), that the $i$th squares of each lines must all meet in the same column. Once you've got this, then you get a 3-partition.

About Question 2, it is obviously hard to give a formal answer, but the general pattern is the following:with 3-partition, you need to introduce some kind of slackness to allow that any integer in an interval $\[min,max\]$ can be somehow encoded and embeded in a slot (which must then correspond to the maximum possible size). But then a common issue is having two integers fitting in the same slot, or more generally other overlapping issues (as with the squares here). This is solved by making sure that the $min$ is large enough compared to the slot size (we often need $min \> max/2$, or $min \> max\*(n-1)/(n)$ here): this is easily achieved with an additive constant $B$.

**Edit** Sample instance where $B$ is necessary: Let the instance of 3-partition be $(10,7,2,10,9,2)$ with $t=20$. This is a no-instance. However, with $B=0$, you have a valid packing of the $40\times 20$ rectangle: use a first column with four squares $(10,7,2,2)$, the last two being side-by-side, and a second column with only $(10,9)$. This is not possible with, say, $B=100$, and a $240 \times 320$ rectangle.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions, np-hard, partitions
---


# Question
Title: How to prove that minimal DFA is unique?
My idea is that the number of states in the minimum DFA is equal to the number of equivalent states. So, if there exists another minimum DFA, then it must have different equivalent states than the previous DFA which is not possible.

How do I formally prove this?

EDIT: Maybe something like "since two states are equivalent, they are semantically equivalent and hence, they can't be equivalent and different at the same time" might do if written formally?

# Answer
Suppose that we are given a regular language $L$ and a DFA ${\cal A} = (Q,q\_0,F,\delta)$. Denote the equivalence classes of the Myhill–Nerode relation of $L$ by $S\_1,\ldots,S\_m$. For each state $q \in Q$, define $L\_q = \\{w \in \Sigma^\* : \delta(q\_0,w) = q\\}$. From the definition of the Myhill–Nerode relation it follows that each $L\_q$ is a subset of some $S\_i$.

The Myhill–Nerode theorem shows that there is a DFA with $m$ states, so suppose that ${\cal A}$ has $m$ states. From our comment above it follows that each $L\_q$ *equals* some $S\_i$. Rename the states so that $S\_i = L\_i$ (so now $Q = \\{1,\ldots,m\\}$). We now read off all the other data of ${\cal A}$:

1. The starting state $q\_0$ is the one whose language contains the empty word $\epsilon$, that is, it is determined by the condition $\epsilon \in S\_{q\_0}$.
2. A state $i$ is accepting if $S\_i \subseteq L$, and rejecting if $S\_i \subseteq \overline{L}$ (it follows from the definition of the Myhill–Nerode relation that these are the only two possibilities).
3. Let $w\_i$ be an arbitrary word in $S\_i$, and let $\sigma \in \Sigma$. Then $\delta(i,\sigma) = j$ if $w\_i\sigma \in S\_j$. Again, the definition of the Myhill–Nerode relation shows that the choice of $w\_i$ doesn't matter.

After renaming the states of ${\cal A}$ in a canonical way, we read off ${\cal A}$ from the Myhill–Nerode relation of $L$. It follows that all minimial DFAs for $L$ are equivalent.
> 3 votes

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


# Question
Title: Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation?
I am following CLRS for studying Amortized analysis with potential function and there I came through the following :

Let a data structure go through states : $D\_0 $ $D\_1$ $D\_2$ $ ....$ $D\_n$ while applying operations $O\_1$ $O\_2$ $O\_3$ $....$ $O\_{n-1}$

$\therefore$ the amortized cost can be written as :

$\hat c(O\_i) = c(O\_i) + \phi (D\_{i+1}) - \phi (D\_{i})$ .

My doubt is that if the state of data structure changes from $D\_{i}$ to $ D\_{i+1}$ that will be due to that cost of $i^{th} $operation which must be equal to the change in potential of the data structure.

So isn't $c(O\_i) = \phi (D\_{i+1}) - \phi (D\_{i})$ ? If not, they why are they not equal ?

Is the potential difference between two states, the overwork (credit) we are doing? If this statement is true, is it the reason for the answer for my doubt to be false?

# Answer
> 2 votes
The potential function is a fictitious quantity which is used to bound the cost of operations in a data structure. Suppose that our data structure supports only one operation, whose worst-case cost is $C$, and that we want to show that the amortized cost is only $\hat{C}$. What we do is define quantities $\phi(D\_i)$ that satisfy the following axioms:

1. $\phi(D\_0) = 0$.
2. $\phi(D\_n) \geq 0$ for all $n \geq 0$.
3. $\hat{c}(O\_i) := c(O\_i) + \phi(D\_{i+1}) - \phi(D\_i) \leq \hat{C}$.

We then have, for all $n \geq 0$, $$ \begin{align\*} n \hat{C} &\geq \hat{c}(O\_1) + \cdots + \hat{c}(O\_n) \\ &= c(O\_1) + \cdots + c(O\_n) + \phi(D\_{n+1}) - \phi(D\_0) \\ &\geq c(O\_1) + \cdots + c(O\_n) \\, . \end{align\*} $$ In other words, the *amortized* cost of each operation is at most $\hat{C}$.

If we define $\phi$ via $c(O\_i) = \phi(D\_{i+1}) - \phi(D\_i)$, then we are really defining some other fictitious quantity. A better choice from the point of view of the analysis above would actually be $\phi(D\_i) = 0$, which allows us to recover the bound $C$. The general idea is that we want the fictitious potential function $\phi$ to generally be "small", but sometimes we allow it to grow (we "borrow") so that we can later on take the cost of a costly operation.

---

Here is a very simple example. Consider a data structure with a single operation in which operation $2^i$ costs $2^i$, and other operations cost $1$. A priori, the worst-case cost is infinite. However, suppose that we define $\phi(D\_n) = 2n - 2^k$, where $2^{k-1} \< n \leq 2^k$, that is, $2^k$ is the smallest power of $2$ above or at $n$ (and $\phi(D\_0) = 0$). Since $n \> 2^{k-1}$, when $n \> 0$ we indeed have $\phi(D\_n) = 2(n-2^{k-1}) \> 0$.

When $2^{j-1} \< i \< 2^j$, we have $$ \hat{c}(O\_i) = 1 + \[2(i+1) - 2^j\] - \[2i - 2^j\] = 3. $$ In this case we are "borrowing", since $\hat{c}(O\_i) \> c(O\_i)$.

When $i = 1$, we get $\hat{c}(O\_1) = 1 + \[2 - 1\] - \[4 - 2\] = 0$.

When $i = 2^j \> 1$, we have $$ \hat{c}(O\_{2^j}) = 2^j + \[2(2^j+1)-2^{j+1}\] - \[2(2^j)-2^j\] = 2. $$ In this case the potential collapses from $2(2^j) - 2^j = 2^j$ to $2(2^j+1) - 2^{j+1} = 2$, allowing us to "pay" for the costly operation $2^j$.

We conclude that the amortized cost per operation is at most $3$.

---
Tags: complexity-theory, asymptotics, amortized-analysis
---


# Question
Title: Does Rice theorem imply that it is not possible to find out the absolute optimum of a physical process?
One of my friends works for a big oil rafinery. He's in charge of optimising the inputs (volumes, maximum price to pay for crude oil etc.) given a profit.

He's telling me there are heuristic ways to find out **local** optima but there is **no way to prove if any of these optima are absolute**.

We were debating on *why* that is. He doesn't know. My theory is that a rafinery is an effectively computable process (Church Turing thesis) hence it's computable by a TM. Now every optimisation problem is a decision problem. So my theory is that tying to find out an absolute optimum for his process would be like finding a decidable non-trivial property of a TM which is impossible (by Rice theorem).

Is that correct?

# Answer
Rice's theorem states that you can't decide a non-trivial property of Turing Machines in general.

You are asking, "given a specific Turing Machine, can I find some property about it." The answer is yes in a large number of cases.

Rice's Theorem says there's no algorithm which can look at *any* Turing Machine and find its optimum.

Your problem is to look at a *specific* Turing Machine and find its optimum. This is likely computable. For example, it's easy to make a Turing Machine which inputs $x$ and outputs $x^2$. Finding the maximum value of this is trivial.

The real question is: what does your search space look like? You're trying to find a local optimum? Of what function, over what inputs? If your inputs are finite and your function computable, then this is certainly decidable. If you're doing things over the Real Line, things get more complicated, but not necessarily impossible, depending on what function you're looking at.

But, if you can show that computing the optimum is equivalent to searching through an infinite search space, and you can simulate *any* infinite (but enumerable) search space with your problem, then you're looking at something Turing Complete, and Rice's Theorem applies.

I suggest you review Rice's theorem, to find what it's actually saying, as well as the difference between an optimization and a decision problem. Every optimization problem is most certainly *not* a decision problem, though you can simulate every decision problem as an optimization problem.
> 4 votes

# Answer
You are estimating that processes at an oil refinery are computable -- that may very well be true.

However, it's unlikely that they are Turing-complete. Unless they are, Rice's theorem does not apply.
> 3 votes

---
Tags: turing-machines, optimization, decision-problem, rice-theorem
---


title: Big-O complexity of sqrt(n)

text:
# Question
Title: Big-O complexity of sqrt(n)
I'm trying to backfill missing CS knowledge and going through the MIT 6.006 course.

It asks me to rank functions by asymptotic complexity and I want to understand how they should be reduced rather than just guessing. The question is to reduce this to big-O notation, then rank it:

$$f(n) = n \cdot \sqrt{n}$$

I see in this answer that $\sqrt{n} \gt \log{n}$

I don't understand how to think about the complexity of $\sqrt{n}$.

What is the complexity class of $\sqrt{n}$?

What is the relationship between $\sqrt{n}$ and $\log{n}$?

# Answer
$\sqrt{n}$ belongs to the class of *sublinear polynomials* since $\sqrt{n}=n^{1/2}$.

From Wikipedia (beware of the difference between Little-o and Big-O notations):

> An algorithm is said to run in sublinear time if $T(n) = o(n)$

Note that constant factors do matter when they are part of the exponent; therefore, we can consider $O(n^{1/2})$ to be different from (and less than) $O(n)$.

With respect to the relationship between $log(n)$ and $\sqrt{n}$, you can find here a discussion about why $\log(n) = O(\sqrt{n})$.
> 8 votes

---
Tags: asymptotics
---


title: Is computation independent of hardware?

text:
# Question
Title: Is computation independent of hardware?
We use electronics to build computers and do computation. Is computation independent of the hardware we use? Would it be possible to do whatever a computer does with pen and paper? If computation is not dependent of how we make our computers, then does the same principle which apply to a computer apply to how brain works? I want to know if computation is an abstract object which then is realized as computers. In other words, if we visit some alien civilization we expect that our mathematicians and physicists understand the alien physics and math. Is it the same as with the notion or concept of computation? It seems that in order to consider computation first we need consider a realization of a machine or a model. For example according to the first two lines of this question there are Turing machine, circuits and lambda calculation. How do we know that there is not another way of computation? For example, the way the brain works and does computation might not be describable by the computation which we consider in Turing machine.

To put it another way, are there axioms which we build a theory of computation based on them? like the way we build Euclidean geometry.

# Answer
To answer the title question, yes, computation is independent of hardware. Computation is defined by the transformation of information, not by how it's embedded in the real world. This is easy to see: all the computation models have a mathematical formulation, and you can write mathematics as symbols on paper. In fact, many models of computation, such as the lambda calculus (1936) and Turing machines (1936) were invented before there were general-purpose computing machines (there were numeric calculators and data sorters, but programmable machines didn't exist until the 1940s).

It is possible to model today's computers by mathematical tools. They're just finite-state machines, after all. There are a lot of states, so a complete pen-and-paper representation is not feasible, but if you only model the part that you're interested in, that can be within reach.

As to whether there is only a single notion of computation, we don't know. We think so: that's the Church-Turing thesis. We think so because we've invented a lot of models of computation, and they all turned out to be equivalent. Some of them are easier to work with than others, or more directly applicable to certain problems, or are a closer match for certain computing hardware (e.g. in terms of performance or locality). But they can express the same computations.

Are Turing machines (or any of the equivalent concepts) the last word on the topic? We don't know. We certainly have *weaker* models of computation, but we think of them as restricted computation. And we have *stronger* models of computation, but we think of them as “magic“ — we can reason about them, but we have no idea how they could be implemented.

Is the brain a Turing machine? That's a question about the brain, and we don't know. We know that it's at least as powerful as a Turing machine, since it can simulate one. We are very far from being able to accurately simulate a brain with a Turing machine, but we don't know whether that's a matter of scale (a brain has tens of millions of neurons — a PC doesn't have enough memory to even store all the connexions). We do tend to think of brains as being more powerful than computers — when a problem is undecidable (in the Turing computation sense), we offer to solve it by thinking, but that doesn't answer the question. When we solve a problem by thinking, the *solution* is expressible in Turing machine terms. The problem solving method, however, may or may not be more powerful than Turing machines.

Would aliens have the same notion of computations? We don't know. We think so — mathematics seems universal to us — but that's a question about aliens, and since we don't know anything about aliens except what your imagination tells us, we can't answer it.
> 9 votes

# Answer
> How do we know that there is not another way of computation?

We do not. Well, we know plenty of Turing-complete and less powerful models. We have also thought about *more* powerful models but we don't know how to build them in reality.

The Church-Turing thesis is our best guess but it can not be proven.

So you are asking for speculation resp. trivialities like this:

> If we had physics that allowed us to store and manipulate real numbers, we could implement Real-RAMs which are strictly more powerful than Turing machines.
> 3 votes

# Answer
"To put it another way, are there axioms which we build a theory of computation based on them? like the way we build Euclidean geometry."

We defined the existence of certain numbers such as the Set of Integers and the Set of Real Numbers via axioms. We have created notions such as variables and relations. We can create linear relations such as linear equations based on these sets. We have proofs (using methods such as the method of substitution) and can solve linear systems of relations in several ways. Every solution is a form of computation. Thus there are axioms (such as those used for sets) which we have built theories of computations.

"Is computation independent of the hardware we use?"

We have adapted the solutions to situations with constraints. For example, there is no practical computer that can represent the elements of the set of Real Numbers or the elements of the Set of Integers. Thus we have fields such as Numerical Methods/Analysis to study how solutions behave using the Set of Floating Point Numbers instead of using the Set of Real Numbers. Thus some computations are dependent on constraints.
> 0 votes

# Answer
in fact,no have the thing to calling the computation.it's just the transformation of energy to some phenomena.but in my opinion,things look like don't depend on the cause or consequence,it's random.Because in the quantum scale,we have no intractable or get out of zeno paradox in the transfer the energy.so they would been in disjointed.so it's no difference if say the event is random,so does computing.
> -3 votes

---
Tags: turing-machines, computation-models
---


title: Prove Θ(n) + O(n^2) ≠ Θ(n^2)

text:
# Question
Title: Prove Θ(n) + O(n^2) ≠ Θ(n^2)
How would I go about proving this statement?

```
Θ(n) + O(n^2) ≠ Θ(n^2)

```

I know how to prove if given a function f(n) if it's big o but I do not understand how to go about this type of problem.

# Answer
> 2 votes
Think of Θ and O as sets (the sets of function satisfying the asymptotic conditions) : you need to prove set difference, i.e. give a function in the left-hand part that does not belong to the right-hand part.

An example would be

$$ f(n) = n + n $$

Clearly $f(n) \in Θ(n) + O(n^2)$. However, $\frac{f(n)}{n^2} = 2/n$, which shows that $f(n)\not \in Θ(n^2)$.

---
Tags: asymptotics
---


# Question
Title: How does O transform this sum like that?
I'm in the process of self-studying the CLRS book. My mathematical background is poor so I'm trying to learn the maths as I go along too.

I don't understand the math in CLRS section 6.4 where they go from:

$$ \sum\_{h=0}^{\lg n} \frac{n}{2^{h+1}} O(h) $$

to:

$$ O\left(n \sum\_{h=0}^{\lg n} \frac{h}{2^h}\right). $$

I understand that the $n$ is moved out to before the sum. But how does the remaining $1/2^{h+1}$ become $h/2^h$?

# Answer
Intuitively, the $O$ can swallow any constant factor. Here, we do so because the sum we get is on the cheat sheet and we can proceed more easily.

Formally, we need to apply the definition of $O$, once in either direction. I do not think the first term makes a whole lot of sense. What the authors *probably* mean is

$\qquad\displaystyle \sum\_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot f(h)$

with some $f \in O(h)$. Then it remains to note that

$\qquad\displaystyle \sum\_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot f(h) \quad\leq\quad \sum\_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot c \cdot h \quad=\quad \frac{c}{2} \cdot n \cdot \sum\_{h=0}^{\lg n} \frac{h}{2^{h}}$

for all $n \geq n\_0$, with $c,n\_0$ the constants from $f \in O(h)$ (unfold the definition). Applying the definition again concludes the proof.

Note that if we had $f \in \Theta(h)$, we would get a similar lower bound and could thus show a $\Theta$-bound for the sum.
> 4 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: How come the branching factor of chess is 35?
I was studying about minmax algorithms and it said the branching factor of a chess game is around average 35. Meaning a player can move about 35 legal moves per position.

I am not able to comprehend this.Like if I do the opening in chess I was able to count 20 possible legal moves.(1 or 2 possible moves for 8 pawns that gives us 16. 2 possible for 2 knights respectively giving a total of 20)

So how it was calculated?

# Answer
Since the moves differ per turn it was calculated as the average. Yes you are right, there are exactly *20* moves in the first turn, but after advancing with knights, bishops, rooks and queen into the center of the board the number of legal moves is increasing and since it is average of the minimax tree also the situation after encrouning with several queens on the both sides is calculated (not very wise game, but still perfectly valid to have more than *100* available moves in one turn.

Please check for some more legal chess positions.
> 3 votes

---
Tags: artificial-intelligence
---


# Question
Title: Kripke Models - evaluating the meaning of $\Box\Box p$
In Kripke models the evaluation of $x \vdash \Box p$ would be that every world reachable from $x$ satisfies $p$.

But how would the truth of $\Box\Box p$ be evaluated in Kripke models?

# Answer
> 10 votes
This is an unfortunate use of the word “reachable”, in that Kripke structures are graphs but “reachable” in a Kripke structure is not the same thing as “reachable” in a graph. Let us avoid this confusion by saying that a state $y$ is a *successor* of state $x$ if there is a (directed) edge $(x,y)$ in the structure.

Now, the semantics of modal logic says that $\Box\varphi$ is true at state $x$ if, and only if, $\varphi$ is true at every successor of $x$. Informally, $\Box\varphi$ means, “$\varphi$ is true everywhere I can get to from here in one step.” So, to understand the meaning of $\Box\Box p$, just substitute $\Box p$ for $\varphi$:

* $\Box p$ is true at every successor
* $p$ is true at every successor of every successor.

In other words, $p$ is true everywhere I can get in two steps. Note that this is not, in general, the same thing as $\Box p$, which means that $p$ is true after one step. Indeed, one can show that $(\Box \varphi)\rightarrow (\Box\Box\varphi)$ is a tautology in a particular Kripke frame if, and only if, the successor relation is transitive.

Note that, without assuming transitivity, basic modal logic with only $\Box$ and $\Diamond$ has no way of expressing “$\varphi$ is true everywhere that can be reached from here, in any number of steps” (i.e., the usual graph-theoretic meaning of “reachable”).

---
Tags: logic, modal-logic
---


# Question
Title: Determine time given algorithmic complexity as input grows?
Consider the time required to solve a problem, represented by `f(n)`, and for sufficiently large inputs of size `k`, the time required to solve a problem is `t`. What is the typical method of determining how long, in terms of `t`, is necessary to solve a problem, for different kinds of `f(n)` and `k`?

For example, when `f(n)` is `Θ(n)`, and the input is `2k`, we know that the time is approximately `2t`. But what is the standard method of determining the time, in terms of `t`, for problems like this? For example:

1. When f(n) is Θ(n3) and the input is k2 ?
2. f(n) is Θ(2n) and the input size is k+3 ?
3. f(n) is Θ(lg n) and the input size is 4k ?
4. f(n) is Θ(n!) and the input size is k+2 ?

This question is not asking for answers to those scenarios per se, rather, how to go about expressing the time, in terms of `t`, given the parameters above.

# Answer
The standard method is to heuristically assume that a bound of the form $\Theta(g(n))$ can be approximated by $Cg(n)$ for some constant $C$, though in some cases this approximation is not justified, and the "constant" $C$ fluctuates (but is bounded on both sides).

Considering your first example, if $f(n) \approx Cn^3$ then $f(k^2) \approx Ck^6 = (Ck^3)^2/C \approx f(k)^2/C$. Unfortunately, the dependence on $C$ cannot be eliminated, but $C$ can be approximated empirically, though you should take such results with a grain of salt.
> 3 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Given an arbitrary language, how does one go about proving that it is recursive or otherwise?
I am having problems knowing how to prove a language is recursive or not. Is there a particular general strategy is used for such a problem, or possibly some principle which is often used?

Thanks very much in advance.

# Answer
> 4 votes
To prove a language is recursive (decidable), use the definition! Show that there exists a Turing machine that always halts and decides the language. Or, use closure properties.

To prove a language is not recursive (not decidable), use a reduction, or use closure properties, or use Rice's theorem. See our reference questions, How to show that a function is not computable? and What are common techniques for reducing problems to each other?.

---
Tags: complexity-theory, formal-languages, computability, turing-machines
---


# Question
Title: How to estimate maximum n given complexity and amount of time?
Say you've implemented a program that completes it's work with O(2n) time complexity, and you measure the actual running time of the program as:

* n1: 0.006s
* n100,000: 16.057s

Since time will grow exponentially as n increases, what is the typical way to estimate the maximum n given a time t? For example, if time t is 1 minute or 1 hour, how do you "correctly" estimate n?

# Answer
> 3 votes
You can't. Mathematically, you can't conclude anything about the running time for all $n$, given just two points (given the running time at just two values of $n$). There are many possible curves that might go through those two curves; two points aren't enough to determine a curve. The running time might be something like

$$\frac{1}{2^{100}} 2^n + n^2.$$

Or, it might be something like

$$\frac{1}{2^{95}} 2^n + \frac{1}{10000} n.$$

Or, the running time might be

$$\frac{1}{100000000} n^2.$$

Or any number of other possibilities.

---

That said, in practice it seems very unlikely that you have an algorithm whose running time on all instances of size $n$ is $\Theta(2^n)$... and yet for $n=100,000$ it completes in 16 seconds. That's a bit silly. In practice, it *could* happen if the algorithm is sufficiently weird, but not bloody likely in practice.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Algorithm for recovering paired lists when elements are broken
I am trying to solve an algorithmic problem. I came from http://math.stackexchange.com upon an advise that this forum would be a better place to ask this.

I would like to hear your advice on where to search for hints. If my problem has got a name, I would like to know what it is called in the field, and what I should learn to solve it. Any partial suggestion would be welcome. Also if there is another forum that fits my question better than here, I would be happy to hear that too.

A description of my problem is as follows. Suppose you have a number of pairs of objects. Let $X$ be the first list of objects and $Y$ be the second list. Assume $X = Y$ in a sense they share the same list of objects.

Now, objects in both lists are "broken" into pieces; Each element $x \in X$ is decomposed to $x\_1, x\_2,...$. The same happens for $Y$. As a result, what you have is two sets $X', Y'$, which contain the broken pieces of the original objects.
The task is to recover the original objects in $X$ and $Y$ from $X'$ and $Y'$.

Here is an example where objects are strings.
Suppose $X = Y = \[apple, banana\]$, and the strings are decomposed as: $X' = \[ban, le, ana, app\]$ and $Y' = \[na, ple, ap, na, ba\]$. I would like to recover $banana$ and $apple$ from information $X'$ and $Y'$.

Does this problem have a name? Or, what do you think the good things to learn for me to study this type of problem?

# Answer
Look at the literature on algorithms for the shotgun sequencing and shortest common supersequence problems. It appears that your problem might not be exactly identical to them, but researchers have developed sophisticated algorithmic techniques for handling this kind of problem. Therefore, I suspect you might be able to use the same techniques for your problem, or adapt them to work well for your situation.
> 2 votes

---
Tags: algorithms, strings
---


# Question
Title: The complexity of the algorithm with loops
I have algorithm that contains next loops:

```
for (int i = 0; i < size; ++i) {

    for (int j = i + 1; j < size; ++j) {
        //Do stuff
    }
}

```

I found that this algorithm has $O(n^2)$ complexity but I can't understand why? I.e. if $N = 4$ then $n^2 = 16$ but my loop has 6 iterations only. Just it's a half of $n^2$ value.

P.S. I understand never how to measure the complexity of the algorithm, I only can understand how to write it in the mathematics.

# Answer
Your "stuff" will get executed $N(N - 1)/2 = 0.5N^2 - 0.5N$ times. When analyzing the asymptotic complexity, only the highest order term is kept, and multiplicative constants are removed, leaving you with $O(N^2)$.

It works this way because we're interested in what happens when $N$ goes to infinity (scalability).
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Covering a directed graph with particular requirements
I'm actually trying to solve a task from an old *OII (Italian national pre-IOI competition)* in which I'm given an **unweighted directed graph** $G$ with $N$ vertices and $M$ edges and I'm asked to find a set of vertices $S$ which satisfies these conditions.
If we call $S^1$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S$, there can't be any vertex in both $S1$ and $S$.
Then we call $S^2$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S^1$.
The set $S$ is a solution to this problem only if every vertex in $G$ is part of at least one of the sets above.
Couldn't think of anything better than an $O(2^n)$ solution, which leads to **TLE**. I'm given a time limit of 3 seconds, with $N \< 1000$ and $M \< N(N-1)/2$.
Something I realized is that I have to consider each different connected part on it's own and some vertices simply must be part of $S$ (if there are no edges starting from another vertex that reach them), but this assumptions didn't help much.

---

I apologize for my english and my poor computer science knowledge, I'm sure some parts should be reformulated but I couldn't find the right words to do that.

# Answer
> 3 votes
This problem is solvable if you have studied computer science, know standard graph problems, can spot a relationship to one of them, and then diligently study what is known about algorithms for that sort of problem.

If this immediately makes you think that it sounds related to some standard, well-known graph algorithm problem (call it Problem X), then go read about what is known about algorithms for Problem X and variants of Problem X. You'll soon find an existing algorithm that can be adapted for this.

If you can't spot any relationship to any graph problem you already know, then you should spend more quality time studying an algorithms textbook. Pick a good algorithms textbook and read it through cover to cover.

---

Alternatively: What algorithm design paradigms do you know? For each paradigm you know of, try to find an algorithm of that type. You should be able to find one for this.

---

I'm not going to say more than this. It's your exercise, so you should have the joy of finding the answer on your own; I don't want to take away from that. Also, practicing problem solving on your own is the best way to strengthen your problem-solving skills. If you just read someone else's solution, you won't learn nearly as much.

---
Tags: algorithms, graphs
---


# Question
Title: Is a physical process with unbounded input Turing equivalent?
Church-Turing thesis states that any effectively computable process is computable by a TM. Let's assume for now that it means that every physical machine is computable by a TM. Let's call it A.

Now if this process has an unbounded number of states (for example we could think of an engine in a car and take the geographic coordinates of the car as its states) we could say that A is also Turing complete.

And therefore Turing equivalent.

**Edit**: Let's try to see more precisely how A could be considered as Turing complete even if the physical is continuous. Let's for example consider a car moved by an engine. And let's consider a planet where towns' names are built with the classic alphabet A, B, C etc. following rules that make the number of towns on that planet potentially infinite or unbounded. Now let's imagine that my vehicle is programmed by an algorithm to drive from town to town indefinitely. **Let's call these towns the states of my system**. Now I am **certain** (but please correct me if I am wrong) that my physical system *is indeed* Turing complete - and not just a push down automaton. Now if you accept that any state an observer (typically a physicist) will use to describe a physical system can be coded in a finite alphabet i.e. an integer (even if the physical world is continuous) then surely we could use the vehicle experience to say that in human eyes the physical world is Turing complete.

Is that correct?

# Answer
No. You can't just sweep everything under the rug like that. The answer depends on what model of reality / physics you subscribe to.

If your model of reality is continuous (e.g., Newtonian physics), then it's not necessarily true that that every physical machine is computable by a TM. TM's are discrete, not continuous; if physics is actually continuous, then your assumption is probably not correct. (It might be true that the outcome of a process can be computed to an arbitrary degree of accuracy by a TM, but that's a subtly different statement. TM's compute discrete values, not continuous values.)

If your model of reality is discrete and finite, then it might be true that that every physical machine is computable by a TM. But now the number of states is not unbounded.

You can't have it both ways. Or, to put it another way, you can't just assume things without justification.
> 1 votes

# Answer
Pushdown automata have unbounded inputs and (potentially) unbounded stack size, hence also an infinite state space. They are still not Turing-complete (not even close).
> 1 votes

---
Tags: computation-models, turing-completeness, church-turing-thesis
---


# Question
Title: Why is C's void type not analogous to the empty/bottom type?
Wikipedia as well as other sources that I have found list C's `void` type as a unit type as opposed to an empty type. I find this confusing as it seems to me that `void` better fits the definition of an empty/bottom type.

* No values inhabit `void`, as far as I can tell.
* A function with a return type of void specifies that the function does not return anything and thus can only perform some side-effect.
* A pointer of type `void*` is a subtype of all other pointer types. Also, conversions to and from `void*` in C are implicit.

I am not sure if the last point has any merit as an argument for `void` being an empty type, as `void*` is more or less a special case with not much relation to `void`.

On the other hand, `void` itself is not a subtype of all other types, which as far as I can tell is a requirement for a type to be a bottom type.

# Answer
> 40 votes
In C, `void` is used for multiple unrelated things. Depending on what it's used for, its meaning may be a unit type, an empty type, or something else.

When `void` is used by itself (as opposed to `void*`, a pointer to void), it's a unit type, i.e. a type with a single value. Functions that return `void` are said to “return nothing”, but what this really means is that they don't return any information. They return $0$ bits of information, which means that they return a value of a type that contains $2^0 = 1$ distinct values, i.e. a unit type.

This is not an empty type: a function that returns an empty type cannot return a value, since there is no value of that type. A function whose return type is empty can only loop forever, or abort the program, or raise an exception (`longjmp`) (or otherwise arrange not to return, e.g. by transferring control to another thread or process using functionality beyond standard C). To keep things confusing, it is conventional in C to use `void` in lieu of an empty type (C doesn't have an empty type).

The `void` type requires $0$ bits of storage. Because C insists on every object occupying a whole, nonzero number of bytes of storage, it's forbidden to create an object of type `void`, and there's a special syntax to return the `void` value (a `return` statement with the value omitted). There's no syntax that yields the value of type `void`, but that value is there whenever a function whose return type is `void` returns.

C does not have a bottom type in the sense of allowing any possible type. Even incomplete types specify the general nature of its values, e.g. pointers or structs or unions or functions. But `void*` is a pointer to any non-function type: it's the least element of the algebra of object pointer types, i.e. it's the bottom object pointer type. Unlike the general case of `*T**` where `*T*` is some non-void type, `void*` is not the type of pointers to a value of type `void`, but the type of pointers to a value of unspecified type.

# Answer
> 11 votes
The name “empty type” is perhaps confusing. What this means is, as you say yourself, *the type contains no values*. The “empty” refers not to any individual values of the type, it refers to the type as a whole, considered as a ~set of possible values. So this does **not** say something like “a function returning `void` returns no information”, but “there *exists* no value of type ”.

This means a function whose result type is  can *never* terminate. If it did terminate, if would have to return a value of , but, well, such a value doesn't exist.

It also means, it's not even possible to discuss how much information a value of empty type would contain, because there is no such value. (Or if you will, a nonsensical statement like “any value of empty type contains exactly 35093658 bits of information” is vacuously true.) It's somewhat useful (though not really correct) to think of  values as containing an *infinite* amount of information.

Whereas a C function with “return type” `void` clearly *can* return, but doesn't give you any information in its return value. Well, that's precisely what characterises a unit type: its values don't contain any information, because there is only one such value (hence you can always say what the return value will be, even without bothering to ever call the function).

To quote Conor McBride (transliterated to C):

> `void` means "Boring". It means the boring type which contains one thing, also boring. There is nothing interesting to be gained by comparing one element of the boring type with another, because there is nothing to learn about an element of the boring type by giving it any of your attention.
>
> It is very different from the empty type \[...\]. The empty type is very exciting, because if somebody ever gives you a value belonging to it, you know that you are already dead and in Heaven and that anything you want is yours.

---
Tags: type-theory, c
---


title: What is the eta-rule for nat?

text:
# Question
Title: What is the eta-rule for nat?
As far as I am aware of, the beta-rule of the natural numbers type `nat` states that (please correct me if I am wrong)

1. `natrec 0 t0 (lambda i ti. ts) := t0`
2. `natrec (succ k) t0 (lambda i ti. ts) := (fun i ti. ts)`

But what does the eta-rule says? I wonder how the following formulation is correct / accurate / complete

`natrec n 0 (lambda i ti. s i) := n`

# Answer
> 6 votes
I do not understand your notation, but the $\beta$-rule is not right (because you write down abstractions). It is: \begin{align\*} \mathtt{natrec} \\; 0 \\; x \\; f &= x \\ \mathtt{natrec} \\; (\mathtt{succ}\\;n) \\; x \\; f &= f \\; n \\; (\mathtt{natrec} \\; n \\; x \\; f) \end{align\*} where $x$ and $f$ are arbitrary (well-typed) terms. (Beware: not every term of a function type is of the form $\lambda x . e$!)

You can read $\beta$ rules as saying what happens when you apply a destructor to a constructor (for instance $\mathtt{fst} (a, b) = a$). An $\eta$-rule says what happens when you destruct a thing and then put it back together (for instance $u = (\mathtt{fst}\\;u, \mathtt{snd}\\;u)$.

We take numbers apart with $\mathtt{natrec}$ and put them together with $0$ and $\mathtt{succ}$, so the $\eta$-rule would be: $$\mathtt{natrec} \\; n \\; 0 \\; (\lambda \\; x\\; m \\,.\\, \mathtt{succ}\\; m) = n.$$

---
Tags: lambda-calculus, type-theory
---


# Question
Title: Why is Brent's Cycle Detection method faster at finding a Linked List cycle than Floyd's Cycle Detection method?
I understand in Floyd’s cycle, you are finding a cycle in a linked list by moving two counters- one by a factor of 2, other by a factor of 1. In Brent’s you are basically doing the same but the one factor moves by multiplying 2 instead by merely adding 2. Is there any math explanation behind why Brent’s is faster than Floyd’s?

# Answer
> 4 votes
The performance of cycle-finding algorithms depends on two parameters $m,n$. Here $n$ is the length of the cycle, and $m$ is the initial position of the cycle. For example, consider the sequence $$ 2, 3, 5, 6, 5, 6, 5, 6, \ldots $$ Here the cycle is $5,6$ and so $n = 2$. The first index of the cycle (assuming $x\_1 = 2$ and so on) is $m = 3$.

We assume that the sequence is generated by repeatedly applying some function $f$. We measure the complexity of cycle-finding algorithms by the number of applications of $f$.

According to Brent's paper, the complexity of Floyd's algorithm is between $3\max(m,n)$ and $3(m+n)$, and that of Brent's is at most $2\max(m,n) + n$, which is always better than $3\max(m,n)$.

A perhaps more meaningful comparison is what happens in the *average* case. In this case we assume that $f$ is a random function on a universe of size $N$ (the starting point doesn't matter in this case). Knuth showed that the expected running time of Floyd's algorithm is roughly $3.0924\sqrt{N}$, whereas Brent's algorithm runs in expected time roughly $1.9828\sqrt{N}$, as worked out in Brent's paper.

For more details, take a look at Brent's paper and the references therein.

---
Tags: algorithms
---


# Question
Title: Linear time algorithms on regular graphs
For each constant $k$, the number of $k$-regular graphs is of the order of $n^{\Omega(n)}$. Therefore, we need $O(n\log n)$ bits to represent k-regular graphs unambiguously.

Let $k=3$ for simplicity. There are several algorithms that run in time $O(n)$ on $3$-regular graphs with at most $n$ vertices. For instance, determining if a graph is bipartite.

How is that possible, if only to read the input we need to read $O(n\log n)$ bits?

# Answer
We usually analyze algorithms on the RAM machine model, in which each operation on a machine word has unit cost. A machine word consists of $O(\log n)$ bits, where $n$ is the bit-size of the input, or some other equivalent property. Thus representing a $k$-regular graph takes only $O(n)$ machine words, so there is no contradiction.
> 5 votes

---
Tags: algorithms, time-complexity, runtime-analysis, lower-bounds
---


title: VC dimension of linear separator in 3D

text:
# Question
Title: VC dimension of linear separator in 3D
I am confused about the Vapnik-Chervonenkis dimension of a linear separator in 3 dimensions.

In three dimensions, a linear separator would be a plane, and the classification model would be "everything on one side of a plane."

It's apparently proved that the VC dimension of linear separators is d+1, so in 3D, its VC dimension is four. That means it should be able to put any set of 1, 2, 3, or 4 points on one side of a plane.

But, what about this case: four coplanar points on a square with opposite corners same adjacent corners different?

```
+1    -1

-1    +1

```

This is the case that a line (2-dimensional linear separator) cannot handle, but the 3-dimensional linear separator is supposed to be able to shatter this. But, I can't see how you could put two corners on "one side of a plane" because all four points are coplanar.

Could someone explain how a 3-d linear separator can shatter the four points I just described?

# Answer
You have a small (but crucial) misunderstanding of what the VC dimension of a class is.

The VC dimension is the maximal number $d$ such that *there exists* a set of $d$ points that is shattered by the class. It doesn't mean that every set is shattered.

In this case, indeed 4 co-planar points cannot be shattered, but if they are placed in a tetraeder then they can be.

This is similar to the case of 2D: 3 points that are co-linear cannot be shattered by a line, but there exists a set of 3 points that can be shattered.
> 11 votes

# Answer
I will simplify it this way- If we can find at least 1 set of d points in an n-D plane, all of whose possible labellings(consider + and - , i.e 2^n), can be shattered, then its VC dimension \>= d. However, if any (atleast 1) of the labellings in that particular set cannot be shattered, then consider another possibility for a set of same number of points d, whose all possible labellings can be shattered,and if found, its VC dimension is at least d and then check for d+1 points, otherwise, its Vc dimension \< d. For instance, VC dimension of a 2D space is 3. This is because for any set of 3 non-collinear points, its all possible labelling(2^3) combinations can be perfectly shattered by a line. However, 3 collinear points cannot be shattered in 2-D plane, because there exists combinations like ((+,-,+), (-,+,-)) that cannot be classified by a line, though other labellings like (+,+,-),(+,-,-), etc. can be perfectly classified. Hence, since there is atleast 1 set of 3 points(non-collinear), all of whose combinations can be shattered by a 2D line, its VC dimension is 3. Hope this helps!!
> 0 votes

---
Tags: statistics, learning-theory, vc-dimension, classification
---


# Question
Title: Are there any examples of programming synthesis in vulnerability research?
## Program Synthesis

To borrow from Microsoft:

> Program synthesis is the task of automatically discovering an executable piece of code given user intent expressed using various forms of constraints such as input-output examples, demonstrations, natural language, etc.

One of the best program synthesis examples I've come across created new authenticated encryption (AE) schemes; the paper also automated the analysis and privacy and authenticity security proofs for the synthesized AE schemes.

The take-away from program synthesis is: (1) it *can* provide novel solutions to solve a problem through an automated process and (2) it is possible to verify the solution's correctness.

## Vulnerability Research & Program Synthesis

There has been a great deal of effort made in recent years in automating vulnerability analysis. A culmination of this effort was demonstrated this summer at the Cyber Grand Challenge(https:// www. cybergrandchallenge.com/).

It would seem like program synthesis would have great potential in automated vulnerability research.

* Perhaps it could derive new exploits
* Perhaps it could derive new patches or tests

My question is this: Are there any examples of program synthesis in vulnerability research?

I am having a hard time finding any examples of such and I would like to know if anyone has come across it.

# Answer
Yes, there's plenty of work on synthesizing exploits using program synthesis. One of the seminal papers was:

Thanassis Avgerinos, Sang Kil Cha, Alexandre Rebert, Edward J. Schwartz, Maverick Woo, and David Brumley. Automatic Exploit Generation. Communications of the ACM, 57(2):74–84, 2014.

This is a cleaned-up and general-audience version of a paper published at NDSS in 2011.

You should be able to use Google Scholar to find lots of other related work and follow-on work, by finding papers that cite it. Also, many of the research teams participating in the Cyber Grand Challenge have been publishing on this subject for the past several years; look up each of their web pages and go check out their papers, and you should be able to find more.

Generally speaking, the challenge typically lies more in finding *inputs* to a vulnerable program that will cause it to do something bad, rather than in finding *programs* that directly do something bad themselves. Thus, the techniques tend to be slightly different from standard work on program synthesis, because the challenges are slightly different in this space: here it's often more about synthesizing data rather than code.

There is also plenty of work on automated patch creation. There, the big challenge is usually identifying which part of the code is vulnerable and what the vulnerability is; once you know that, the patch synthesis is usually rather straightforward. Consequently, the challenge typically seems to be more about program *analysis* than *synthesis*, though of course there are certainly aspects of both that do need to be solved, and different papers have a different focus.
> 2 votes

---
Tags: reference-request, security, program-synthesis
---


# Question
Title: Algorithm to determine minimum server required?
So I came across a problem that has be completely stumped. You're given *n* servers to store a file on and you need to find the minimum number of servers you need to store the file on so that you can minimize the cost of the client and to the user.

When the user tries to look for a file he will start at some unknown server, check to see if the file is there and if it's not will move on to the next server and do the same. The cost is the minimum distance between the user and the server with the file.

To upload the file to the i'th server it would cost the client c\_i

The exception is that you can upload it to the n'th server for a cost of 0 (meaning that the user will never have to loop around and the worst case won't be n)

So basically I need to find an algorithm that will find a subset that will give us a balance between the cost to the client and the cost to the user.

# Answer
> 0 votes
This answer assumes that what you're trying to minimize is $$ \sum\_{i \in S} c\_i + \sum\_{i=1}^n d(i,S), $$ where $c\_i$ is the cost of the $i$th server and $$d(i,S) = \min\_{\substack{j \in S \\ j \geq i}} \\; j-i$$ is the distance from $i$ to the closest server.

Use dynamic programming. For all $j \leq j\_0$, compute the minimum of $$ \sum\_{i \in S} c\_i + \sum\_{i=j}^n d(j,S) $$ over all $S \subseteq \\{j,\ldots,n\\}$ such that $\min S = j\_0$.

---
Tags: algorithms, algorithm-analysis, optimization, search-algorithms
---