title: Reduction from SAT to shortest cycle?

text:
# Question
Title: Reduction from SAT to shortest cycle?
I have been assigned a homework problem that I cannot figure out:

> Prove that SAT has a polynomial-time reduction to the language of undirected non-negative weighted graphs with simple cycle of weight less that or equal to w.

This bears a resemblance to the all-pairs shortest path problem which has polynomial-time algorithms, but I've read multiple times that this problem is np-hard (plus, I suppose it would be a cruel trick to give such an assignment).

Starting from hamcycle, I have managed to produce a reduction for several variations on this problem (e.g., tsp, longest positive path, shortest negative path), but whenever it comes to this language I can always come up with a counterexample that invalidates my attempt at a reduction.

So, is there a reduction from SAT? What am I missing?

# Answer
> 1 votes
In the spirit of "give a man a fish, and he'll be fed for a day; teach a man to fish, and he never need be hungry again", I'll share with you some problem-solving techniques that might be helpful for approaching this problem (and other problems) -- but I'm not going to spoil it for you by solving your exercise for you.

---

Technique #1: If you don't know how to solve a problem, change the problem: look for "nearby"/"similar" problems you do know how to solve. If you can't reduce SAT to the original language, is there some related/variant language you *can* reduce SAT to? You may need to try multiple variants, and get a feeling for which ones you can easily find a reduction for and which ones you struggle with. This may give you some intuition about what the barrier/difficult part of your problem is, which may help you identify what aspect to focus your energy on.

Hint #1 (possible spoilers):

> If you changed "less than or equal to w" to "equal to w", would the problem be any easier? What if you changed it to "greater than or equal to w"?

---

Technique #2: You can chain reductions. If you can reduce SAT to some variant, and reduce that variant to the original problem, you're in business.

Hint #2 (possible spoilers):

> It seems that short cycles are a headache. If you have a graph $G$, can you think of some way to transform it to remove all short cycles (without changing whether or not it contains a cycle of length $w$)? (If you can't immediately see how to do it, can you write out a precise specification of what such an algorithm would need to do?)

---

And that's as much as I'm going to say. It's a good exercise, and it's your exercise, so you should have the chance to play around with it and discover a solution for yourself. It's tricky but doable.

---
Tags: complexity-theory, graphs, reductions, satisfiability
---


# Question
Title: What is a proof of normalization of Morte?
It is said that any term on the calculus of construction halts. I am studying it through Morte, which is a bare bone implementation of the coc available on github. Is there any simple proof of normalization for the calculus of constructions? If the proof isn't simple, is there an simple intuition behind the result?

# Answer
I'm afraid there is no simple proof of the normalization for the CoC, as it implies the consistency of a very strong form of logic.

A good reference is Geuvers, A short and flexible proof of strong normalization for the calculus of constructions.

The intuition of the proof is hard to convey, but basically it is shown that for each type $T$, there exists a notion of "term computable at type $T$", which is a predicate, intuitively a subset of the set of $\lambda$-terms. A computable term has good properties, in particular it is always normalizing. Building this notion of computability involves building a kind of model for the CoC, often called a realizability model.

Then it is shown that any well typed term $t:T$ is computable at type $T$.
> 2 votes

---
Tags: type-theory, functional-programming, turing-completeness
---


# Question
Title: Is it possible to add "memory" to a neural network?
Suppose I have a NN with one hidden layer, 10 inputs and 5 outputs, intended to be used as a (for example) game-bot AI. Would it make any sense to add, say, 5 (insert any number here) more inputs and outputs, and directly link these outputs from a previous step to these additional inputs of the next?

I imagine it could work as a RAM of sorts, making it possible to "save" some data that the network finds useful and use it later, therefore enabling the network to make decision not only on the current situation, but also on whatever it may "remember".

But maybe it's better to just hard-code these variables as actual variables and write only what the programmer decided to, such as "enemies killed", without the network being able to save whatever it finds useful?

# Answer
> 4 votes
Yes it is possible. Recurrent neural networks address this issue. They are networks with loops in them, allowing information to persist.These loops make recurrent neural networks seem kind of mysterious. However, if you think a bit more, it turns out that they aren’t all that different than a normal neural network. A recurrent neural network can be thought of as multiple copies of the same network, each passing a message to a successor.

Visit http://colah.github.io/posts/2015-08-Understanding-LSTMs/ : This blog explains Recurrent Neural Network(RNN) and LSTM from scratch and also discuss few examples where LSTM is preferred over RNN.

# Answer
> 1 votes
The answer is "it depends on what you're trying to accomplish", so I don't think we can answer this without more context. But you might want to look at recurrent neural networks and LSTM networks, which do something along the lines you mention. LSTM networks have been effective for some kinds of tasks that involve processing data sequentially, with "memory", so depending on what you're trying to accomplish, they might be suitable for your application.

Generally, in machine learning, it's hard to know a priori what approach is going to work best. Instead, you have to try many different approaches and evaluate how well each one works on a large set of data with known ground truth (e.g., using cross-validation).

# Answer
> 1 votes
From a programmatic point of view, this is trivial to do. For the training you will have to know the appropriate values for the extra inputs, which will be the extra outputs at the same time.

---
Tags: neural-networks
---


# Question
Title: Does Dijkstra's Algorithm actually check nodes marked as visited?
I guess this is an implementation question, but I suppose it can be answered for the typical way this algorithm works.

So, most ways the algorithm has been explained to me involve going from a source vertex to another vertex so on and so forth. Will any edges going back to the source vertex or any already visited vertex actually get looked at, or does the algorithm ignore those because they already have their shortest path set up.

# Answer
It depends on the implementation, but generally those edges are considered, but the algorithm immediately notices the target node is already visited or the new distance is greater than the old one, and doesn't process the edge further.
> 2 votes

# Answer
I've heard previously of implementations that used a visited array, but instead I simply mark each node with the starting value of `Integer.MAX_VALUE` or similar, of course under the assumption that no node will actually need that long of a path to get to that large of a number. Afterwards, with the condition that you only update the node if `prevNode + distance < currentNode`, this will work since `prevNode + distance` is less. Just be careful to never add anything to unvisited nodes otherwise it overflows.
> 0 votes

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Graph searching: Breadth-first vs. depth-first
When searching graphs, there are two easy algorithms: **breadth-first** and **depth-first** (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).

Now, are there any advantages of one over another?

The ones I could think of:

* If you expect your data to be pretty far down inside the graph, *depth-first* might find it earlier, as you are going down into the deeper parts of the graph very fast.
* Conversely, if you expect your data to be pretty far up in the graph, *breadth-first* might give the result earlier.

Is there anything I have missed or does it mostly come down to personal preference?

# Answer
I'd like to quote an answer from Stack Overflow by hstoerr which covers the problem nicely:

> **That heavily depends on the structure of the search tree and the number and location of solutions**.
> If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might rootle around forever, but BFS could be faster. If the tree is very wide, a BFS might need too much more memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).
>
> But these are just rules of thumb; you'll probably need to experiment.

Rafał Dowgird also remarks:

> Some algorithms depend on particular properties of DFS (or BFS) to work. For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node.
> 48 votes

# Answer
One point that's important in our multicore world: BFS is much more easy to parallelize. This is intuitively reasonable (send off threads for each child) and can be proven to be so as well. So if you have a scenario where you can make use of parallelism, then BFS is the way to go.
> 38 votes

# Answer
(I made this a community wiki. Please feel free to edit.)

If

* $b$ is the branching factor
* $d$ is the depth where the solution is
* $h$ is the height of the tree (so, $d\le h$)

Then

* DFS takes $O(b^h)$ time and $O(h)$ space
* BFS takes $O(b^d)$ time and $O(b^d)$ space
* IDDFS takes $O(b^d)$ time and $O(d)$ space

Reasons to choose

* DFS
    + must see whole tree anyway
    + you know $d$, the level of the answer
    + don't care if the answer is closest to root
* BFS
    + answer is close to the root
    + you want the answer that is closest to the root
    + have multiple cores/processors
* IDDFS
    + you want BFS, don't have enough memory, but somewhat slower is acceptable

IDDFS = iterative deepening depth-first search
> 38 votes

# Answer
One scenario (other than finding the shortest path, which has already been mentioned) where you may have to choose one over the other to get a correct program would be infinite graphs:

If we consider for example a tree where each node has a finite number of children, but the height of the tree is infinite, DFS might never find the node you're looking for - it will just keep visiting the first child of every node it sees, so if the one you're looking for isn't the first child of its parent, it will never get there. BFS however is guaranteed to find it in finite time.

Similarly if we consider a tree where each node has an infinite number of children, but the tree has a finite height, BFS might not terminate. It will only visit the children of the root node and if the node you're looking for is the child of some other node, it won't be reached. In this case DFS is guaranteed to find it in finite time.
> 17 votes

# Answer
Breadth-first and depth-first certainly have the same worst-case behaviour (the desired node is the last one found). I suspect this is also true for averave-case if you don't have information about your graphs.

One nice bonus of breadth-first search is that it finds shortest paths (in the sense of fewest edges) which may or may not be of interest.

If your average node rank (number of neighbours) is high relative to the number of nodes (i.e. the graph is dense), breadth-first will have huge queues while depth-first will have small stacks. In sparse graphs, the situation is reversed. Therefore, if memory is a limiting factor the shape of the graph at hand may have to inform your choice of search strategy.
> 16 votes

# Answer
All of the above is correct, but it's noteworthy that BFS and DFS create their own trees, based on the order they use to traverse the tree. Each of those trees has it's own property which can be useful in some sort of problems.

For example, all the edges in the original graph which are not in the BFS tree are cross edges; edges which are between two branches of the BFS tree. All the edges in the original graph which are not in the DFS tree are back edges; edges which connect two vertices in a branch of the DFS tree. Such properties can be useful for problems such as special colorings, etc.
> 3 votes

# Answer
DFS and BFS tree both have their own unique properties that can give you more useful information about the graph. For example with a single DFS you can do the following:

* Find bridges and articulation points (for undirected graphs)
* Cycle detection
* Find strongly connected components (Tarjan's algorithm)

With BFS, you can find the shortest paths between the source node and any other nodes in the graph.

The Graph Algorithms chapter in CLRS sums up these properties of DFS and BFS very nicely.
> 1 votes

# Answer
I think it would be interesting to write both of them in a way that only by switching some lines of code would give you one algorithm or the other, so that you will see that your dillema is not so strong as it seems to be at first.

I personally like the interpretation of BFS as flooding a landscape: the low altitude areas will be flooded first, and only then the high altitude areas would follow. If you imagine the landscape altitudes as isolines as we see in geography books, its easy to see that BFS fills all area under the same isoline at the same time, just as this would be with physics. Thus, interpreting altitudes as distance or scaled cost gives a pretty intuitive idea of the algorithm.

With this in mind, you can easily adapt the idea behind breadth first search to find the minimum spanning tree easily, shortest path, and also many other minimization algorithms.

I didnt see any intuitive interpretation of DFS yet (only the standard one about the maze, but it isnt as powerful as the BFS one and flooding), so for me it seems that BFS seems to correlate better with physical phenomena as described above, while DFS correlates better with choices dillema on rational systems (ie people or computers deciding which move to make on a chess game or going out of a maze).

So, for me the difference between lies on which natural phenomenon best matches their propagation model (transversing) in real life.
> -2 votes

---
Tags: algorithms, graphs, search-algorithms, graph-traversal
---


# Question
Title: W[1]-hardness of Steiner tree w.r.t. number of non-terminal vertices
This is an exercice is Rolf Niedermeier's book "Invitation to fixed-parameter algorithms", Chapter 13.

Show that the following problem is W\[1\]-hard: Steiner Tree in Graphs with respect to the parameter "number of non-terminal vertices".

The way I understand it, if there are most $k$ non-terminal vertices, then this doesn't help in solving the Steiner problem in time $f(k)n^c$.

The objective is to find the minimum number of edges connecting terminal vertices (while some vertices are non-terminal). I can't find a reduction however. I am convinced that the parameter $k$ being number of *included* non-terminal vertices in a solution makes it W\[2\]-hard. But if $k$ is the number of existing non-terminal vertices, I don't know. Proof ideas or references will be appreciated.

# Answer
When parameterized by number of non-terminal vertices *in the input graph*, Steiner Tree is FPT by brute force.  -  Find a minimum-size subset of non-terminal vertices such that \[the subgraph induced by the union of \[the set of terminal vertices\] with \[the chosen set of non-terminal vertices\]\] is connected, and then output any spanning tree of that subgraph.

(If that's not your interpretation of the problem, then clarify your last paragraph.)
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Efficient immutable data structure for small multi-sets of integer ranges?
# Background

I'm currently writing some Elixir algorithms that are quite computationally expensive. The most-used datastructure is a multi-set of (finite) integer ranges. Modifying this data structure takes up around 80% of the execution time in `insert` and `remove`, so it's time to see if there's something better out there. I'm spending around 1400 clock cycles per `insert` or `remove`, so there should be some margin for improvement.

# Current implementation

The current model, called `Domain`, is a fully persistent immutable ordered linked-list of `[low, high)` pairs, normalized so that for any time two ranges overlap, the first one is the longest. Touching ranges are also joined. Most domains consist of less than 100 ranges, but some consist of up to 10k ranges. The current data structure is chosen because it was easy to work with, avoiding premature optimization.

The `Domain` datastructure represents a multiset of integers. Internally representing ranges as `[low, high)` pairs is just an optimization. Since some domains cover many million of numbers, I don't think a multiset would be fast enough to be viable.

A range is a set of `b-a` unique integers `x`, `a <= x < b`, distinct from every previously defined range, with `b-a` as large as possible.

# The operations

The operations supported right now are

* `insert(a,b)` union of two domains, keeping duplicates
* `remove(a,b)` `a` minus `b`
* `intersection(a,b)`
* `ncov(a,n)` `a` with `n-1` copies of each present integer removed.
* `after(a,n)` domain of everything in `a` equal to or greater than `n`
* `before(a,n)` domain of everything in `a` equal to or smaller than `n`
* `minlen(a,l)` domain of all ranges in `a` with a cardinality of at least `l`.
* `trunc_start(a,l)` `a` with the `l` smallest integers removed from each range.
* `trunc_end(a,l)` `a` with the `l` largest integers removed from each range.

Queries:

* `contains?(a,p)` does the domain `a` contain a specified integer `p`?
* `covers?(a,b)` is domain `b` a subset of domain `a`?
* `lowest(a)` what's the lowest integer in the domain?
* `highest(a)` what's the highest integer in the domain?

# Behaviour

The most common use-case is to modify the structure a small bit at a time, from smallest value to biggest. Since inserts might modify the whole structure, the lists are almost always rebuilt completely right now. Changing the access pattern to bulk inserts and deletions is not feasible.

The second most common use-case is intersection between multiple (3+) domains, currently implemented as repeatedly calling the binary intersection function.

# Questions

* Is there a standard name of this data structure?
* Is there a more efficient format? If so, which one(s)?
* Would a tree be faster than a linked-list? With or without rebalancing?

# Answer
I would suggest looking at interval trees and segment trees. A natural representation is that the data structure contains a union of non-overlapping ranges $\[l,u\]$ with a multiplicity $m$; the intended meaning is that each integer in the range $l,l+1,l+2,\dots,u$ occurs in the domain with multiplicity $m$ (i.e., appears $m$ times), and the invariant is that the multiplicity of all integers within a single range is the same.

We can't tell you whether a tree would be faster in your application; that's workload-dependent, so the only way to tell is to try it and benchmark it and see.

This can be made persistent using standard techniques (e.g., path copying), if that's useful (e.g., if you have many domains that are similar to each other).
> 2 votes

# Answer
The Google Guava library has a RangeSet data structure that might satisfy some of your requirements. You can check out its implementation to see if it is what you need.

https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/RangeSet.html
> -1 votes

---
Tags: data-structures, efficiency, sets, intervals
---


# Question
Title: Find the duplicates in a list of floating point numbers
I receive a list of real numbers ( `float` ) between $0$ and $1$. The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ apart. Here is an example test case:

```
[ 0.        ,  0.31662479,  0.63324958,  0.94987437,  0.26649916,
  0.58312395,  0.89974874,  0.21637353,  0.53299832,  0.84962311,
  0.1662479 ,  0.48287269,  0.79949748,  0.11612227,  0.43274706,
  0.74937186,  0.06599665]

```

One possibility I came up with is to multiply by $N=17$ and to take the integer part:

```
[ 0,  5, 10, 16,  4,  9, 15,  3,  9, 14,  2,  8, 13,  1,  7, 12,  1]

```

Then I have to find the location of two numbers in this list which are identical.

---

I would appreciate any solution to this problem with or without the intermediate multiplication step. Or does this problem have a particular name in the field of algorithms?

# Answer
> 3 votes
## Sorting

The simplest algorithm is to sort your floats, then compare adjacent entries. This will let you find all pairs that are $\le \frac1N$ apart in $O(N \lg N)$ time.

## Hashing

It's also possible to come up with a linear-time algorithm, i.e., to check whether there is any nearby pair of floats and if so find at least, in $O(N)$ time.

Let $M=\lfloor N/2 \rfloor$. Build a list of integers by replacing each float $x$ with $\lfloor Mx \rfloor$, then find all duplicates in the resulting list of integers. Finding duplicates in a list of integers can be done in expected linear time by hashing and looking for a pair with the same hash. For each duplicate integer, check whether it corresponds to a pair of floats that differ by $\le \frac1N$.

Then, do it again: build a second list of integers by replacing each float $x$ with $\lfloor Mx + 0.5 \rfloor$, then find all duplicates in this list and check each to see whether it corresponds to a pair of floats that differ by $\le \frac1N$.

It's possible to show that if there exists a pair of floats that differ by $\le \frac1N$, then this procedure will find at least one such pair; and if there aren't any such pair, then this procedure will discover that fact. Moreover, with suitable choice of the hash function, this can be made to run in expected linear time. In fact, if you replace the hashing with counting sort, this runs in deterministic linear time.

## In practice

In practice, my advice is to simply sort and then compare adjacent entries. It will be easier to implement, less fiddly (you don't have to deal with corner cases), obviously correct, and probably more than fast enough in practice.

# Answer
> 1 votes
This is a special situation: If we have n+1 values from 0 to n, there *must* be two values that are only 1/n apart. You can obviously find these by sorting the array and checking for two elements close together in O (n log n), but you can do faster.

There is a well known algorithm for finding medians or percentiles roughly based on the Quicksort algorithm: You start with an array with indices from 0 to n-1. One step of the Quicksort algorithm divides the array into a smaller and a larger half. Quicksort would then sort each half. Instead you decide which half contains the median or percentile you're interested in and process that half. You can do something similar.

Start with l = 0, r = n, low = 0, high = 1: The array elements at indices l to r are all \>= low and \<= high, and this implies there is a pair at most 1/n apart.

With the Quicksort algorithm, you would find an array element p (the pivot) and move all elements \<= p to the left, all elements \>= p to the right. You will get a \[k\] = p for some k. Then the elements from l to k are all between low and p, the elements from k to r are all between p and high. One of these ranges will guarantee two elements at most 1/n apart, so you change l, r, low, high accordingly.

You need to take some precautions to make this work: First, repeat this method until r - l ≤ 2. If r - l ≤ 2, sort the array and get the right values.

In the Quicksort algorithm, it can happen that little progress is made. In this algorithm, if you are not careful, no progress is made. If the pivot is chosen equal to low or high, no progress will be made. In that case, pick a second pivot, then a third. Lucky enough, if you picked three pivots equal to low or high, then you found a solution!

---
Tags: sorting, integers, floating-point, lists
---


# Question
Title: Where can I find a data set of graphs with known domination numbers?
I implemented an algorithm to find the minimum dominating set of a graph. I want to check the output of the algorithm against some graphs for which the domination number has been determined.

Where can I find graphs with a known domination number?

# Answer
> 3 votes
One place to look is House of Graphs, which is a database of "interesting" graphs. For instance, there are graphs that have been used as counterexamples to various conjectures, have extremal properties with respect to some parameter, and so on. For more, see \[1\].

Another possibility is using Mathematica, which also has a database of graphs accessed through its GraphData-function.

---

\[1\] Brinkmann, G., Coolsaet, K., Goedgebeur, J. and Mélot, H., 2013. House of Graphs: A database of interesting graphs. Discrete Applied Mathematics, 161(1), pp.311-314. --- Free version at arXiv

---
Tags: graphs
---


# Question
Title: What is the difference between following two finite automata?
I'm solving problem of drawing the finite automata of `(1+0)*(10)`. Which is any string ends with `10`. I've drawn the following diagram for this one:

But somewhere in solution it is given the following diagram:

I can't understand what is the difference between these two? Is my solution is correct? If it is not than what changes in my solution will take me to this given solution?

# Answer
> 5 votes
As many have pointed out in the comments, your automata is non-deterministic. There are two paths you could take from `q0` when you read a `1`. When running a non-deterministic automata, you need to keep track of all possible paths and see if any of them end up in an accepting state. If you don't keep track of all different possible states you could be in, your solution might never accept any string, if it choses the looping `1` all the time, never leaving `q0`.

Converting a non-deterministic finite automata (NFA) to a deterministic finite automata (DFA) can be done using a simple algorithm. It's quite slow, but for small examples, it's no problem doing it by hand. There are good videos explaining how to do this in slightly different ways.

The main idea is that you build a table of all possible states you could be in. For your NFA, I'll label the nodes `q0`, `q1` and `q2` from left to right, starting at `q0`.

* At `q0` we can reach `q0` or `q1` when reading a `1`.
* At `q0` we can reach `q0` when reading a `0`.

That's the first step. Now we have multiple states at the same time. We already did `q0` so we have the (`q0` or `q1`) state left.

* When reading a `1` from (`q0` or `q1`) we can end up in (`q0` or `q1`). `q0` can reach (`q0` or `q1`), and `q1` cannot reach anywhere.
* When reading a `0` from (`q0` or `q1`) we can end up in (`q0` or `q2`). `q0` can loop back to itself, and `q1` can reach `q2`.

And lastly, the (`q0` or `q2`) state.

* When reading a `0` from (`q0` or `q2`) we can end up in `q0`. `q2` doesn't have any outgoing edges, and `q0` can only reach itself.
* When reading a `1` from (`q0` or `q2`) we can end up in (`q0` or `q1`). `q2` doesn't have any outgoing edges, and `q0` can reach (`q0` or `q2`).

Those are all our possible state transitions in the NFA.

Our list of states used in the transitions above are:

* `q0`
* (`q0` or `q1`)
* (`q0` or `q2`)

The edges are:

* `q0` \+ `0` -\> `q0`
* `q0` \+ `1` -\> (`q0` or `q1`)
* (`q0` or `q1`) + `0` -\> (`q0` or `q2`)
* (`q0` or `q1`) + `1` -\> (`q0` or `q1`)
* (`q0` or `q2`) + `0` -\> `q0`
* (`q0` or `q2`) + `1` -\> (`q0` or `q1`)

You can see that this is the bottom graph in your question, with the states renamed.

It's worth noting that in real life regex engines, NFA's are used because this conversion is very expensive for large automata. It's cheaper and safer to keep track of all states instead of doing the conversion. One notable example is the RE2 library. Most other implementations use backtracking, which is `O(2^n)` for an `n`-length string. RE2 is exponential in the expression length, but linear in input. Developers write the expressions, attackers write the input.

# Answer
> 2 votes
The difference is that yours is a Nondeterministic finite automaton, given a symbol $1$ of the string you can either stay in state $q\_0$ or go to state $q\_1$, but how do you decide which one? (remember that both **DFA's** and **NFA's** have no memory!).

That's when you have a non determinism, you keep consuming symbols of the string, at some point you make a guess "Well I'm in the last two symbols of my given string, lemme see if I can reach the end State", if it ends with $10$, then you'll go to $q\_1 \rightarrow q\_2$, otherwise you'll remain in $q\_0$.

The solution given in your book is an equivalent **DFA**, as it was already told in the comments you can take your **NFA** and convert it to an equivalent **DFA**.

# Answer
> 0 votes
Both are right answers. The finite automata you have drawn is actually NFA (Non-deterministic Finite Automata) And in the Second diagram (the answer in solution) is DFA (Deterministic Finite Automata)

As the name suggest, Non-deterministic, NFA may have more than one transition from a state for a single input symbol. That is, in your first diagram On seeing input symbol 1 at q0 state, the machine can remain in q0 itself or it can go to next state. But in DFA, for every state you need to define **EXACTLY ONE** transition for **each** input set.

Now, an answer to your doubt is the second diagram is more appropriate. Why..??!! Because every language has many finite automata. That is for language (1+0)\* 10 , I can draw many NFAs and Many DFAs.

*But every regular language has **unique minimal DFA** and that minimal DFA should be your answer for such type of question.*

For minimization of DFA, you may refer following links. (1) Link-1 (2) Link-2

Note that, you can first draw NFA and convert it to equivalent DFA. But it is not the only way. By practice, you can directly draw the DFA for the given regular language.

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


# Question
Title: Is there another common name for dominating set in graphs?
I am looking for graphs which the value of a minimum dominating set is known (Where can I find a data set of graphs with known domination numbers?). So far I have not found anything, so perhaps I missed a search term. Does anybody know if dominating set goes by some other name?

# Answer
> 4 votes
No, *dominating set* is a common name, and I've never seen another name for the definition. You might get luckier if you search for *domination number* though, that's the *size* of a minimum dominating set.

---
Tags: graphs, terminology
---


title: Why is PH in PSPACE?

text:
# Question
Title: Why is PH in PSPACE?
$PH \subseteq PSPACE$.

In order to prove it, one has to show that for a language $A \in \Sigma\_k$ (for some $k \in \mathbb{N}$) there exists a turing machine $M\_A$ that decides it in polynomial space.

I am having a hard time understanding why this is true. I'll try to explain:

Let's take for example $L \in\Sigma\_2$: by definition, $x \in L \Longleftrightarrow \exists y\_1\forall y\_2 : V(y\_1,y\_2)=1$. But finding such $y\_1$ and checking it against all possible $y\_2$s has to take more than polynomial space! The machine has to remember each $y\_2$ that it tried in order to make sure that it indeed tried out all of the options, and the number of possible $y\_2$s is exponential, which makes it exponential space.

# Answer
> 10 votes
No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, just remembering the last one is enough.

---
Tags: complexity-theory, complexity-classes, space-complexity
---


# Question
Title: Formal notion of a call graph for Turing machines
To most computer programs one can assign a "call graph". Is there a formal notion of call graphs of Turing machines?

Motivation is, that one could intuitively call a decidable language $L$ "irreducible" if every Turing machine which decides $L$ has a "trivial call graph" (Trivial here intuitively means, that the machine $M$ which decides $L$ can not call another machine $M'$ during the computation on words). This would intuitively correspond to the notion that "irreducible problems" cannot be solved by breaking them up into smaller problems, for example by divide and conquer.

Another motivation is to understand the concept of composition of Turing machines, which is "equivalent" to understand what is meant when one speaks of "subroutines" (which one could call a "submachine").

# Answer
> 8 votes
Turing machines have no concept of "calling".

Tou can jump to another state and that can look quite a lot like a procedure call, especially if an author's description of the machine in English uses words that make it sound that way. But that's *all* you can do. In particular, there's no notion of "return" in a Turing machine. There's no way to say "OK, this procedure is finished – now go back to wherever we came from." All you can do is say "OK, this procedure is finished – now go to this specific point."

Of course, because Turing machines are Turing powerful, you can *simulate* these things. For example, you can write some notion of a return address on the tape as part of your simulation of a procedure call. But that's not intrinsic to Turing machines: it's just a property of the particular Turing machine you're writing at the moment. A coding convention, if you like.

# Answer
> 4 votes
For TMs, there is no such notion and there can not be. Compare plain TMs with assembler: there are rudimentary operations which together create some effect, but there is little to know syntactic structure.

The concept of procedure calls you have in mind only exists in higher-level programming languages, namely such that have introduced *abstractions* you can use to *modularize* your code in a clear way. Compilers take these concepts and translate them into rudimentary code: procedure calls become unconditional jumps with some maintenance code around them.

Looking at the compilate, you won't be able to determine a call graph per se: there are no procedures anymore, just a huge blob of code with jumps in all directions.

The situations with TMs is similar. In proofs, we use higher-level descriptions in an informal way; we expect that every informed reader would, in principle, be able to create a real TM following our sketch -- to compile, essentially. The resulting machine would bear little resemblance to the original description.

Of course, you can happily talk about "call graphs" in these languages -- just don't expect the notion to carry over to TMs any more than a call graph in C carries over to, say, MIPS assembler.

# Answer
> 2 votes
Quoth Hopcroft and Ullman:

> A Turing machine can be formally defined as a 7-tuple $M = \langle Q, \Gamma, b, \Sigma, \delta, q\_0, F \rangle$ where
>
> * $Q$ is a finite, non-empty set of *states*
> * $\Gamma$ is a finite, non-empty set of *tape alphabet symbols*
> * $b \in \Gamma$ is the *blank symbol* (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
> * $\Sigma\subseteq\Gamma\setminus\\{b\\}$ is the set of *input symbols*
> * $\delta: (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma \times \\{L,R\\}$ is a partial function called the *transition function*, where $L$ is left shift, $R$ is right shift. (A relatively uncommon variant allows "no shift", say $N$, as a third element of the latter set.) If $\delta$ is not defined on the current state and the current tape symbol, then the machine halts.
> * $q\_0 \in Q$ is the *initial state*
> * $F \subseteq Q$ is the set of *final* or *accepting states*. The initial tape contents is said to be ''accepted'' by $M$ if it eventually halts in a state from $F$.

Note that lack of a notion of "calling" anything. A Turing Machine executed the steps prescribed by its transition function. There is nothing you could call, because there is no program, no notion of a method, nothing but the transition function.

Other formalisms might be more amenable to defining a call-graph. Things like a RAM for example.

---
Tags: turing-machines, programming-languages, data-flow-analysis
---


# Question
Title: Why updating only a part of all neural network weights does not work?
I am having a problem with my program of deep neural network using Theano. In my deep neural network, I have several layers of neural network to predict an output given a certain input. Because of an issue when compiling theano, I have to debug my program step-by-step. Since Theano gives me an error when updating weights of some layers, I perform a check by calculating the derivatives of only the last layer (using `tensor.grad` if you know Theano). But if I do that then the network will not update properly and the cost does not decrease and the output is nowhere close to the true output. **It seems like updating the weights of only the last layer does not seem to train the network to learn.**

Is it mandatory to update all weights of all layers in a deep neural network to decrease the cost? What I understand is that if I fix the values of all weights except the weights of the last layer, it should still be able to predict correctly after many rounds of training (of course, the only layer that is learning is the last layer, but I accept that, I only needs the predicted values to be close to my true values while training).

I hope my explanation make sense to you. If you do not understand any part, I will gladly provide you more information.

# Answer
If you're only changing the weights in the last layer, then effectively you have a neural network with a single layer, preceded by some preprocessing step. Single-layer neural networks (also known as perceptrons) aren't so powerful.

Why isn't the network learning anything? It doesn't learn much because it *can't* -- a single-layer network can't learn complicated functions.
> 5 votes

---
Tags: machine-learning, neural-networks, gradient-descent
---


# Question
Title: Get term type during evaluation using Hindley-Milner type system
I've implemented a lambda calculus evaluator and use the Hindley-Milner algorithm to infer terms types and ensure type correctness without the user having to explicitly annotate types.

But now I'd like to add a `typeof` operator that given a term, it returns the type of the term. So far, what I do is keep a hash map of terms to types that is populated during type checking. So if I do `typeof 123`, when the type checker determines the type of `123`, it'll add `123 = Number` to the hash map and look it up when `typeof 123` is evaluated.

The problem with this approach is that if I have this term:

```
let _typeof = \a.(typeof a) in (_typeof 123)

```

Since `\a.(typeof a)` is polymorphic and has type `a -> Type`, the result will be `a` instead of `Number` as I'd expect. If instead I had this:

```
(_typeof.(_typeof 123) \a.(typeof a))

```

Then I'd get the right type `Number` since `\a.(typeof a)` is not polymorphic.

So all I need is a way to handle polymorphism. I'm having a hard time getting my head around it and I wonder if there is a known way to do this.

# Answer
> 2 votes
Hashing of terms to types sounds like a hack to me (or possibly premature optimization and a hell created by stateful programming). During type inference you should tag *every* subterm with its computed type. Then during evaluation `typeof` simply projects the type.

The hell is in the deatils, of course. Here are some initial thoughts about how this would go (I did not actually implement this, but if I did, I would start from Poly in PLZoo).

We define the following datatypes:

* a datatype `ty` of polymoprhic types
* a datatype `preterm` of raw terms (the parser gives you these)
* a datatype `term` of tyepchecked terms (type inference converts preterms to these)
* a datatype `value` of values

Maybe like this, using OCaml syntax:

```
(* the result of parsing is a preterm *)
type preterm =
  | PreType
  | PreNumeral of int
  | PreTypeof of preterm
  | PreVar of string
  | PreLet of string * preterm * preterm
  | PreApp of preterm * preterm
  | PreLambda of string * preterm

type ty =
  | Type (* the type of all types *)
  | Number
  | Parameter of int
  | Arrow of ty * ty

(* after type inference every term is tagged with its type *)
type term = term' * ty
and term' =
  | Type
  | Numeral of int
  | Typeof of term
  | Var of int (* using de Bruijn indices *)
  | Let of term * term (* using de Bruijn indices *)
  | App of term * term
  | Lambda of term (* using de Bruijn indices *)

(* a typing context *)
type ctx = ty list

(* a runtime environment *)
type env = value list

(* values are explicitly tagged with their types *)
and value = value' * ty
and value' =
  | ValType of ty
  | ValNumeral of int
  | ValLambda of env * term

```

The parser gives us a `preterm`. Then we define

```
infer : ctx -> preterm -> term

```

and an evaluator

```
eval : env -> term -> value

```

The evaluator now has an easy time evaluating `typeof e` as

```
let rec eval env = function
  ...
  | Typeof e ->
    let (_, t) = eval env e in
      (ValType t, Type)
  ...

```

Let us work through your example

```
let _typeof = (λ x . typeof x) in _typeof 123

```

First, `infer` would find out that `_typeof` has type `α -> Type`. In the application `_typeof 123` it would try to match (a fresh instance of) `α` against the type `Number` and would succeed with setting `α = Number`. It would then conclude that the type of `_typeof 123` is `Type`.

Second, when `eval` gets to evaluation of `_typeof 123` it actually sees something like

```
(App ((Var 0, Arrow (Parameter 0, Type)), (Numeral 123, Number)), Type)

```

which is an application of bound variable `0` to the numeral `123`, together with typing information: the bound variable `0` has type `Arrow (Parameter 0, Type)` which corresponds to `α -> Type`, the numeral has type `Number`, and the entire expression has type `Type`. The evaluator first evaluates

```
(Var 0, Arrow (Parameter 0, Type))

```

which involves looking up the `0`-th variable in the environment. It gets back a pair `((env', e), Arrow (Parameter 0, Type))` where `(env', e)` is a closure representing `λ x . typeof x`. Then it evaluates the argument and gets `(ValNumeral 123, Number)`. It remains to evaluate `e` applied to `(ValNumeral 123, Number)` which is done the usual way with a recursive call to `eval` in `env'` extended with `(ValNumeral 123, Number)`. Here `e` is going to be something like

```
(Typeof (Var 0, Parameter 0), Type)

```

which corresponds to the expression `typeof x`, except that `x` is replaced by de Bruijn index `0` and is tagged to have "any type". Now we need to pay attention (here is where you have a mistake that gives you `α` instead of `Number`): we first evaluate `(Var 0, Parameter 0)` by looking up the `0`-th elemenent of `(ValNumeral 123, Number) :: env'`, so we get `(ValNumeral 123, Number)`. Now we evaluate `Typeof` by taking the second component, which is `Number`. It would be *wrong* to evaluate `Typeof` by simply returning `Parameter 0`, we actually have to evaluate its argument and then take the type of that). The final value therefore is

```
(Type Number, Type)

```

as expected.

# Answer
> 1 votes
You may want to consider the approach Haskell uses to solve this problem, which is to say via typeclasses. A typeclass is a set of functions that can be implemented by many types. When a polymorphic function needs to be able to call such a function on a type that is unknown, it is silently modified to add an extra parameter, the "dictionary" for the type's instance of the type class (which is a structure containing the functions for that type's instance). Then call sites where the actual type is known are silently modified to pass the correct instance, and so on.

Then you just need a type class "Typeable" that is automatically defined for all types and which contains an appropriate "typeOf" for each defined type.

This may not be the *easiest* way of achieving what you want, but it leaves you with extremely useful general mechanism for solving many kinds of polymorphism problems, so it might be the most *useful* way of achieving what you want.

Simplifying the way this works in Haskell slightly (because AIUI Haskell's implementation involves an optimization that is conceptually unnecessary):

The typeclass `Typeable` is translated to a record type containing a function `forall a . a -> Type`. The function `typeOf` is defined with type `Typeable a => a -> Type` which means that there is an implicit parameter of type `Typeable`. `typeOf` is defined to simply unwrap the function from the record and call it.

A polymorphic function that calls `typeOf` needs to get a dictionary for its type argument, so any such function is inferred to have type `Typeable a => [whatever the type would have been originally]` for any type variable `a` that it needs to call `typeOf` for. This also means that there is an implicit argument to this function, too.

A function that calls `typeOf` for a known type has to provide an argument for the implicit arguments. This is calculated during the type checking phase, and it picks an appropriate predefined instance for the type of the term (which it obviously knows, because it has just type-checked it).

So in your example from the comments, the type checker knows that the term `typeOf` is applied to has type `[Number]` so it picks an instance for that type and adds that as a parameter.

So far, this is just the usual implementation of typeclasses. The twist here is that the type checker treats `Typeable` as a special case and *generates the instances itself on demand* so there will always be an instance available for any type that exists in the program.

It may also be worth noting that the instance for `[a]` can potentially delegate to the instance for `a` and wrap/otherwise modify the result. This may reduce the number of instances that are required.

---
Tags: lambda-calculus, type-checking, type-inference
---


# Question
Title: Are two strings equal if all deciders for a language take the same amount of time for both?
Let $X\_\*^L$ be the set of all deterministic Turing machines $M$ which decide the language $L$ and have the property:

$\forall x,y \in \Sigma^\*: t\_M(xy) \ge t\_M(x) + t\_M(y)$ (\**)

where $t\_M(w)$ is the time of $M$ on input $w$.

Define for all $x,y\in \Sigma^\*$:

$d(x,y) := \max\_{M \in X\_\*^L} \frac{|t\_M(x) - t\_M(y)|}{t\_M(xy)+t\_M(yx)}$

Then, because of (\**) we have $t\_M(yx) + t\_M(xy) \ge 2(t\_M(x)+t\_M(y))$ from which it follows that: $\frac{|t\_M(x) - t\_M(y)|}{t\_M(xy) + t\_M(yx)} \le 1/2 \frac{|t\_M(x)-t\_M(y)|}{t\_M(x) + t\_M(y)} \le 1/2 \frac{ |t\_M(x)| + |t\_M(y)|}{t\_M(x) + t\_M(y)} = \frac{1}{2}$ Hence we get $d(x,y) \le 1/2$.

My question is this:

Does $d(x,y) = 0$ which is equivalent to $\forall M \in X\_\*^L: t\_M(x) = t\_M(y)$ imply that $x = y$?

The reason for asking this question, is that I am trying to define a metric on strings which has "something to do with the time-complexity of Turing machines". If we define $d(x,y) = \max\_{M \in X^L} |t\_M(x) - t\_M(y)|$ (where the maximum is taken over all machines which decide $L$.). Then I can show, that $d(x,y) = 0$ implies $x = y$. But the problem with this definition, is that $d(x,y)$ can be $\infty$. Or am I wrong with this?

# Answer
> 3 votes
Your "distance" $d(x,y)$ is never zero for distinct, non-trivial $x$ and $y$.

Let $M$ be a decider for $L$ and $x,y \in \Sigma^\*$ with $\varepsilon \neq x \neq y$. Let furthermore $T = 1 + \max \\{ t\_M(x), t\_M(y) \\}$. Now we construct a machine $M'$ like this:

```
M'(z) {
  if x == z or xy is a prefix of z
    wait for T steps
  return M(z)
}

```

We observe that $t\_{M'}(x) - t\_{M'}(y) \geq T \> 0$ since $x \neq y$. Condition (\**) is satisfied by increasing the running-time on all inputs that begin with $xy$ as well; hence, $M' \in X^L\_\*$ and thus $d(x,y) \> 0$.

This constructions works for all pairs of distinct $x$ and $y$, proving the claim. Your claim follows since trivially $d(x,x) = 0$ for all $x$.

---

I think the problem is that $d(x,y)$ is not well-defined. With a similar construction as above, we can increase the difference between $t\_M(x)$ and $t\_M(y)$ by an additional $i$ for all $i \in \mathbb{N}$. Since the sum of $t\_M(xy)$ and $t\_M(yx)$ grows with $i$ as well (unless either is $\varepsilon$), $d(x,y)$ approaches a constant for $i \to \infty$ and the maxium does not exist.

# Answer
> 2 votes
Raphael's answer explains why $d$ as defined doesn't work. You stated that you want a metric, ideally. To explain why you will have trouble defining it with any kind of max/min relating running time: for every string x in L, there is a machine that first reads in the input, checks if it is x, and if so immediately returns; otherwise it resorts to some "standard" machine's algorithm. Thus, for every x, there is a machine that checks x in linear time.

It is possible to define a metric in runtime on *languages*, instead of strings. For instance, dividing them into classes such as P, (NP-P), and (Decidable-NP), we can define a metric between two languages that is 1 if they belong to the same class, or 2 otherwise. This of course can be generalized to any number of runtime classes, and this discusses the minimum (over machines) of the supremum (over strings in the language) of runtime, as compared to input length. This gets around the "hard code a given string" problem.

If you really want a metric for strings relevant to their position in the language, min and max clearly don't work, so you must use some type of averaging. This will require defining a measure over machines of interest, or somehow weighting the machines based on their runtimes on other inputs. However, all the constructions I could think of for this would end up very sensitive to the particulars of the construction of Turing machines, or vulnerable to similar "hard coded answer" problems.

---
Tags: turing-machines, strings, string-metrics
---


# Question
Title: Polynomial time solution for bipartite matching
Inspired by this StackOverflow question, I am wondering if there is an *efficient* algorithm for the following problem:

> Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all items labelled alphabetically. Each item has a *disallow* list: there are certain boxes that item cannot be put into. Generate a mapping of items to boxes that does not violate any item's disallow list.

For bonus points, I would be interested in being able to generate all such mappings.

---

At first blush, the problem appears to be the inverse of the stable marriage problem, in that everyone has a strict list (rather than an ordinal ranking) of whom they *don't* want to get married to but will settle for anyone else (and strictly speaking the men/boxes have no preferences). *Edit: it appears this problem is closer to bipartite matching.*

A very naive solution is to simply generate all permutations and check which ones don't violate any disallow lists, but this grows as $O(n!)$. Are there any *polynomial* time solutions out there?

# Answer
This actually has nothing to do with the stable marriage problem; it's an instance of bipartite matching. (It's not related to stable marriage, becuase you don't have an ordering on the preferences of which box each item is matched to; you just have a list of what's allowed or disallowed.)

There are efficient algorithms: use the Hungarian algorithm, or any other algorithm for finding a maximum matching in a bipartite graph. See https://en.wikipedia.org/wiki/Bipartite\_matching#In\_unweighted\_bipartite\_graphs, https://en.wikipedia.org/wiki/Hungarian\_algorithm, and https://en.wikipedia.org/wiki/Assignment\_problem.
> 3 votes

---
Tags: algorithms, permutations, bipartite-matching, assignment-problem
---


# Question
Title: Master Theorem and rounding up to the nearest integer
For the master theorem for recurrences of the form

$$T(n) = a\\,T\\!\left(\tfrac{n}{b}\right) + f(n)\\,,$$

what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/b$? My guess is that this would only allow splits that are natural numbers, and obviously you can't split into a non-integer number, but I can't see anything beyond that.

# Answer
Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:

1. Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).
2. Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing), and the master theorem *will* apply for sure to $n$ of that form.

So, the standard proof of the master theorem will show that $T(n) \le f(n)$ *when $n$ is a power of $b$*. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $b$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg\_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.
3. A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.
> 6 votes

---
Tags: recurrence-relation, master-theorem
---


title: Detecting events in time series data

text:
# Question
Title: Detecting events in time series data
I am collecting data from a sensor over time, and I'm trying to figure out how to detect "events" in the data - specifically, when a given event begins and ends. The frequency, duration, and amplitude of these events varies.

Rather than using some rules-based scheme that proves to be rather ineffective, I want to train a model to detect these events for me. An example of my data (in only one dimension; I have multiple variables that I'm reading) looks like this:

There's one event here and some baseline data on either side.

My raw data before and during this event looks like:

```
1/1/2016 12:48:03   14.2
1/1/2016 12:48:04   12.8
1/1/2016 12:48:05   13.6
1/1/2016 12:48:06   13.5
1/1/2016 12:48:07   12.9
1/1/2016 12:48:08   15
...
1/1/2016 12:48:34   27.7
1/1/2016 12:48:35   30.3
1/1/2016 12:48:36   31
1/1/2016 12:48:37   32.8
1/1/2016 12:48:38   31.1
1/1/2016 12:48:39   28.7
1/1/2016 12:48:40   32.1
...

```

I have training data consisting of raw readings and timestamps that I can correlate to a truthset of event start and end times, but I don't know how I should go about featurizing to build a model. I assume I would keep a window of, say, 30 seconds or a minute of readings. (Events are typically more than a minute long, but I don't know whether I would need my window to contain the entire event.)

I'm familiar (but not an expert) with regression and boosted trees, and I know of tools that can generate code I can use without third-party libraries. But I don't know whether these are feasible approaches to solving my problem.

How can I go about detecting these events?

**Edit**: After some discussion, I've created the following graph to show what more data might look like from different signals. The duration of the manually labeled event is in blue (using the right axis labeled 0/1). Three signals show up strongly:

* Red covers the overall event reasonably well and is essentially the above example
* Purple-blue has an even stronger signal but only for the first half or so of the event
* Yellow-green has a stronger signal than reed for maybe a third of the event, but basically after purple-blue dies off.

Some signals (eg, the bottom-most orange on the left side) have an increase during the event. These either have a weak signal that should be captured or have no signal; however, it's not obvious whether any correlations between these signals and events exist, and if so, how to extract them.

# Answer
Your first step is to characterize what effect you expect an event to have on your signals. Does it change the mean? Increase the mean? Change the variability? The more you can say about the type of effect it will have, the more specific a test you'll be able to build, and thus the more effective any analysis is likely to be.

Then, your second step is to apply appropriate techniques from the statistics literature on time series analysis. There are many techniques that look applicable here:

I recommend you start with some exploratory analysis. Based on the underlying physics/mechanics of how your system works, try to identify some ways that an event might affect the resulting signals. Also, do some exploratory data analysis: find some examples of known events, visualize the signals during those time periods, and hypothesize some feature values that seem to be affected during the signal (e.g., the mean got larger; the standard deviation got larger; the mean of the absolute value of the first derivative got larger; something like that). Finally, look for appropriate techniques in the statistical literature. If you can characterize the effect of an event well, you might be able to use change point detection techniques that will work well. If you can't characterize the effect of an event, you might need to fall back to some kind of machine learning, trained using a large training set... but you should still do each of the steps I listed, to help you identify what features might be useful to use in your machine learning model.
> 6 votes

---
Tags: machine-learning, data-mining
---


# Question
Title: How to resize a large, distributed hash table?
Many hash table implementations found in programming languages (such as Java's HashMap or Python's dict) dynamically increase the size of the hash table once the number of items reaches a certain threshold. In these cases, resizing the hash table means allocating a new, larger memory area, re-hashing all the items and moving them from the old to the new memory region. Because resizing is done "rarely", insertion is still O(1) amortized.

This may be fine if the hash table is stored in memory and if the number of items is relatively small, however what about large distributed hash tables?

Suppose that I have a cluster of 100 PostgreSQL databases, each one containing terabytes of data. What happens if I add a new database to the cluster? Will all the items be re-hashed and moved around? I strongly doubt that, as the operation could take several days to complete.

Hence my question: what is the strategy adopted in those cases?

# Answer
> 5 votes
Yes, after storing many items in a distributed hash table spread over a hundred computers, if hypothetically we used the sort of hash function popular for in-RAM hash table, adding another computer would cause every item to be re-hashed and nearly every item to move from one computer to another, which could take days.

So instead we use special hash functions specifically designed for DHT applications, which allow us to add computers and more-or-less immediately start using them and only re-arrange a few items. (Ideally, with around 100 computers, about 1 percent of the items in each and every computer already in the DHT would move to the new computer). Confusingly, some people use "consistent hashing" to refer to *any* such system where relatively few items are re-shuffled when a new computer is added or removed from the system, although most use "consistent hashing" to refer to the one particular such system described below.

I now know of 4 different hash algorithms solve the distributed hash table problem, all of them (coincidentally?) published in 2001. (Are there others?)

* rendezvous hashing, also called highest random weight hashing (HRW): A client with a list of computers Cj looks up some key K by giving each computer a score Sj = hash( K | Cj ). The key, value pair K,V is stored on the computer with the highest score. (For two-failure-tolerant systems, the key,value pair K,V is stored on the *three* computers with the highest scores).
* consistent hashing: A client with a list of computers Cj maps each computer to a location on the the edge of a circle. The client looks up some key K by starting at the point where K maps onto the circle, and walking clockwise until it hits a computer. (Each computer is actually mapped to many "replica" points on the edge of the circle). (For two-failure-tolerant systems, the key,value pair K,V should be stored on the first *three* different computers it walks across). The "distance" walked is d = (unsigned int)(hash(K) - hash(Cj)). In some implementations, such as Chord and Pastry, none of the computers nor the client really knows *all* of the computers in the DHT. The client sends a request to a few of the closest computers ''that it knows'', asking about the key. Each such computer either responds with the (key, value) data item if it has it, or with a list of other, closer computers.
* content addressable network (CAN) has some similarities to consistent hashing, except instead of a one-dimensional circle-edge, it uses a multi-dimensional torus.
* Kademlia algorithm: A client that only knows about a few of the computers in the DHT looks up some key K by finding the computers that are "close" to the key, where the "distance" is calculated as d = hash(Cj) XOR hash(K). (This abstract "distance" function is completely uncorrelated with the real, physical distance in miles between servers). The client sends a request to a few of the closest computers ''that it knows'', asking about the key. Each such computer consults its tables and reply with a list of the closest computers to the desired key ''that it knows''. The client sends a request to a few of *those* ever-closer computers, asking about that key, and repeats that process until no new nodes are returned that are closer than the best previous results. (For two-failure-tolerant systems, the key,value pair K,V should be stored on the three "closest" computers to that key K).

There is one additional technique often used to make adding a new computer to a DHT appear "instantaneous": indirection. Immediately after adding a new computer to a DHT system, most items should remain in the same place, but there are typically lots of items that need to move from each old computer to the new computer -- it may take a day before all those items are moved, typically as a low-priority "background task". Long before all those items are moved, each old computer sends a brief summary of those items to the new computer, and when some client asks the new computer for some particular item, the new computer either (a) admits to the client it doesn't have that file yet, and tells the client which one of the old computers still has that item, or (b) bumps up the priority of moving that item to a "foreground task", possibly streaming each block of that item to the client as soon as it is received from the old computer.

# Answer
> 1 votes
I think I found the answer: **consistent hashing**.

Relevant links:

---
Tags: data-structures, distributed-systems, hash-tables
---


# Question
Title: Is there a connection between the halting problem and thermodynamic entropy?
Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem.

A TM is an abstract concept of a machine (or engine if you like). The Halting Theorem is an impossibility result. A Carnot Engine (CE) is an abstract concept of a heat engine and Carnot proved the Carnot Theorem, another impossibility result related to thermodynamic entropy.

> Given that a TM is physically realizable (at least as much as a CE, or maybe not?) is there a mapping or representation or "isomorphism" of TM or CE which could allow to unify these results and in addition connect to entropy?

There are of course formulations of TM and the Halting Theorem in terms of algorithmic information theory (e.g. Chaitin, Kolmogorov etc.) and entropy (in that context). The question asks for the more physical concept of entropy (if in the process of a potential answer algorithmic entropy arises it is fine, but it is not what the question asks exactly).

One can also check another question in physics.se which relates quantum uncertainty with the 2nd law of thermodynamics. See also: an algebraic characterization of entropy, an algorithmic characterization of entropy, a review and connections between various formulations of entropy

# Answer
I am not at all an expert in this area, but I believe you will be interested in reversible computing. This involves, among other things, the study of the relationship between processes that are physically reversible and processes that are logically reversible. I think it would be fair to say that the "founders" of the field were/are Ralph Landauer and Charles H Bennett (both of IBM research, I think.)

It touches on quantum computing and quantum information theory, but also examines questions like "what are the limits of computation in terms of time, space and energy?" It is known, (if I remember correctly) that you can make the *energy* required to perform a *reversible* calculation arbitrarily small by making it take an arbitrarily long time. That is, energy $\times$ time (=*action*) required to perform a reversible computation can be made a constant. This is *not* the case for non-reversible computations.

Many of the people studying in this area are also working on quantum computing and digitial physics (the idea that the universe is a big quantum cellular automata). The researchers names that come to mind are Ed Fredkin, Tommaso Toffoli and Norm Margolus.

These questions are *absolutely on topic* for computer science. Not just for the theory (which includes cool math as well as cool physics) but for engineers who want to know the ultimate limits of computation. Is there a minimum volume or energy required to store a bit of information? The *action* required to perform a reversible computation may be constant, but are there limits on what that constant is? These are critical knowledge for engineers trying to push the boundaries of what is possible.
> 13 votes

# Answer
I'm not familar with Carnot's Theorem, except what I've just read in Wikipedia, but even from that cursory introduction, there is a connection in the *structure* of the proofs, and that may be interesting to you, as it's a proof technique that is applicable in many domains.

They're both proofs by contradiction in which to show that no thing in a given class has some property, you suppose that some instance actually does have that property, and then show that a contradiction follows.

The Halting Problem is interesting in that the contradiction arises from some self-interaction concerning the particular instance (which is a machine M that can determine whether an arbitrary machine will halt with a given input). In particular, you construct a new machine that includes M as a component, and then feed the new machine to M.

Someone with more knowledge about Carnot's Theorem could elaborate on it (which I'm not qualified to do), but it appears that the contradiction arises from the type of heat engine that you could build if you had an instance with the property at hand.

So both cases involve the construction of:

* Suppose some X has property P.
    + From X, build related Y.
    + The relationships between X and Y are contradictory.
* Therefore, no X has property P.

There does appear to be a difference, though, in that the contradiction in the Halting Theorem case is a pure logical contradiction, and would be contradictory in any setting of classical logic. The Carnot Theorem, as I understand it, is only contradictory with respect to the second law of thermodynamics. From a logical perspective, that's an axiom, so if you took a different axiomatization in which the second law of thermodynamics didn't hold, Carnot's Theorem wouldn't be a theorem, because the contradiction wouldn't exist. (What a formalization of thermodynamics would look like without the second law is the sort of question that led geometers to non-Euclidean geometry.)
> 6 votes

# Answer
IANAPhysicist but I don't see any connection. Turing machines are objects of pure mathematics and the undecidability of the halting problem is independent of any physical realization of anything.
> 4 votes

# Answer
this diverse multiple-topic question unf does not have a simple/easy answer and touches on active areas of TCS research. however it is a rare question asking about a link between physics & TCS that has interested me over the years. there are a few different directions to go on this. the basic answer is that its an "open question" but with some active/modern research touching on it and hinting at connections.

* there are some surprising/deep undecidable problems from advanced physics. for example from dynamical systems. however, have not seen this connected to entropy per se, but entropy is associated with all physical systems (eg one can see this in chemistry theory), so there must at least be an indirect link.
* entropy indeed shows up in CS but more in the form of information theory and coding theory. the birth of coding theory involved the definition/analysis of entropy associated with communication codes by Shannon. try this great online ref Entropy & Information theory by Gray
* entropy is also associated sometimes associated with measuring randomness in PRNGs. there is a connection of complexity class separations (eg P=?NP) to PRNGs in the famous "Natural Proofs" paper by Razborov/Rudich. there is continuing research on this subj.
* you mention thermodynamics and its connection to TCS. there is a deep connection between magnetization in spin glasses in physics and NP complete problems studied in the SAT transition point. there (again) the physical system has an entropy associated with it but it has probably been studied more in a physics context than a TCS context.
> 2 votes

# Answer
There is a simple thought problem that is sometimes used as an introduction to non-conventional computing paradigms:

*You have two light bulbs and their respective on-off switches. Someone opens and closes both lights one after the other. How do you determine which one was closed first and which one was closed last? Determine the minimal number of times you will need to open the lights to decide this problem.*

Most computer scientists usually try to find some boolean logic-based solution. The answer is (at least one of them): by touching the light bulbs and seeing which one is hotter.

Heat-based paradigms exists in computer science: simulated annealing is an known algorithm (D-waves quantum computer is the quantum counterpart of the algorithm).

Now is there a relation with the Halting problem?

The classic work of Chaitin and Calude on the Halting problem via the concept of Omega numbers can be linked to the probabilistic formulation of the Halting problem. It is the more recent treatise on the problem that I can think of... and no clear relation with entropy (thermodynamic). Now if information entropy (in the sense of Shannon) is good with you, the Omega number encodes in the most succinct way the Halting problem, in the sense of a Shannon bound.

In short, an Omega number is the probability that a random program halts. Knowing the constant would allow the enumeration of all valid mathematical statements (truths, axioms, etc.) and is uncomputable. Calude computed a version of Omega by changing the uniform probability measure with a measure inversely proportional to a random program's length and by using prefix-free encodings.So we could speak of Chaitin's Omega and Calude's Omega.
> 1 votes

# Answer
Yes!, strangely enough I have thought about this.. Here is the idea:

**First Step**

Model the Maxwell's Demon as a computer program. Then, *How does Demon came to know particle's speed and position before opening the door for selection?*

Suppose that the demon can't measure the speed at which particles hit the door, why? because that would change particle's speeds, so demon have to figure out *before* open it, without looking, without measuring. To be fair we will let the demon know the rules of the game in advance, i.e. feed the demon with laws of motion, interactions of particles, and initial conditions, enough of the physics/dynamic model.

**Second Step**

Now model the gas of particles also as a computer program that is running same code given to the demon for every particle, so the gas is computing a result from its initial conditions, the Demon doesn't know that result until it halt (if ever): namely "a particle with the right speed is at the door", the decision yes/no question we are asking to the system is "Have a particle the right position and enough speed?", if so, the door could be opened and the fast particle can go into the high temperature side of the room setting new initial conditions (will those consecutive problems has an answer? or will run forever?)

*There will be a time when there is no particle with enough speed to cross the boundary, so, there will be a time when the code will run forever (do not halt) for almost any given threshold.*

Demon wants to know the result that is computed by the gas, but the result is in a sense involved potentially within the source code of the particle's laws plus the initial conditions.. of course we need to run that program to know it. If Demon run the same program waiting for the right speed at the output, the program could halt or it could run forever (but we suppose also that demon has no more computational power than the gas, so it won't be able to decide the door opening on time ).

Daemon could try to figure out the program output (or if it will halt) by watching the source and inputs *without running it* but it's like trying to solve the Halting Problem, why? because *Demon doesn't know what laws and initial condition will be feed* so Demon should be prepared to solve for any set of law and initial conditions, and we know it's not possible in general, it will need an oracle, if it could it will be enough to build a demon to generate energy from nothing. (even knowing the laws and initial condition, both things already enough hard to know)

This thought experiment can link how *a reduction in entropy, by mean of computers, could in some way bounded by Halting Problem*, as a problem to anticipate in general the outcomes.

(Sometime all limits seems to be the same limit..)

**More about Particle Laws**

Particle's laws are not the main issue of this thought experiment, those laws could be quantum or classical, but we must have into account the fact of complexity of laws and initial conditions, the complexity of the arrange of particles is not bounded, and it could have a lot of added complexity (in an extreme example of initial conditions you could even insert a whole computer firing particles according to an internal source code and give that code to the daemon).
> 0 votes

# Answer
Very captivating question indeed, and we will see that **your thinking IS correct**.

First let's see what the second principle of thermodynamics says.

The entropy function is used in the 2nd law of thermodynamics. It stems from Carnot's theorem which states that processes taking places in steam machines have an efficiency lower or at best equal to the corresponding "reversible" machine (which by the way seems like an unstable concept over the 150 years of thermodynamics). Carnot did not coin the entropy function himself, but together with Clausius this is what they say:

*As there is no perpetuum machine, then we can build a function S called entropy which constrains macroscopic thermodynamic measures into a certain equation, namely that* **S(V, T, P, etc.) = 0**

Note that this equation is nothing but the equation of a hyper-surface in the space of thermodynamic measures.

**Enters Carathéodory.**

Carathéodory is a German mathematician and like all mathematicians he wants to extract out of Carnot's and Clausius reasoning some axioms which would allow him to clarify what the second law *really* is about. Put bluntly he wants to purify thermodynamics to know exactly what entropy is.

After listing a certain number of axioms, he manages to formulate HIS second law, which says (more or less):

*There ARE some adiabatic processes. Or more prosaically, if you want to return, sometimes work alone is not enough. You need a bit of heat.*

Now that seems VERY different from the formulation of Clausius! But in fact it it not. All Carathéodory did was to change the orders of the words, a bit like mathematicians played with Euclide's 5th axiom for 2,000 years and produced many different wording for that axiom. And if you take a step back you should not be too surprised by Carathéodory's statement of the second law. In fact Carathéodory's leads to the exact same entropy function and hyper-surface equation **S(V, T, P, etc.) = 0**

Think hard on Carnot's theorem. As a mathematician, you should not be too satisfied of the way Carnot's admits perpetuum machines do not exist. In fact, as a mathematician you would rather see something like this:

*There is an entropy function S which constrains macroscopic measures IF AND ONLY IF there is no perpetuum machines".*

NOW you have a theorem. And what does it say? That as long as there is no *isolated mechanical* system which produces an infinite amount of energy and hence could lead you to any state you want, then you will find an entropy function. An *isolated mechanical* system is an adiabatic process. Hence Carathéodory's formulation: no adiabatic system can lead you anywhere. Sometimes you will need some heat.

So not only we are sure that Carathéodory's is correct, but also that his formulation is pretty simple.

Now where do you get the impression that the second law à la Carathéodory is similar to the halting problem?

Take a step back on Carathéodory's statement. All it says is that **once you have an isolated mechanical system which you stop mingling with, you cannot reach any state you want.**

Doesn't that sound PRECISELY like the halting problem? I.e. once you have written all axioms of your theory and laid down all possible transitions, there will be problems which you cannot solve. **Sometimes, you will need to add more axioms.**

In fact if you want to go really deep and encode Carathéodory's formulation, this will result in the same code as the halting problem with adiabatic processes instead of Turing machines, and states instead of problems.

What do you think?

**NOTE: I edited my answer almost entirely so comments below won't be in line with what it contains now.**
> 0 votes

---
Tags: turing-machines, halting-problem, entropy
---


# Question
Title: What is the best terminology for lower bound
The term lower bound comes from math and applies to more than just complexity theory. What we see is that such and such is "a" lower bound. In complexity theory should this not be phrased as "the" lower bound, or better still the lowest bound. I can see where lower is a relative term, but the complexity of a given problem would seem to have exactly one minimum. Am I being overly semantic here? what I would like to say is that the lower (or lowest) bound on the complexity of SLL(k) testing is exponential.

http://www.slkpg.com/NPcoNP.html

# Answer
> 1 votes
If you want to talk about the complexity of a problem, just use "the complexity of the problem" and don't bring lower bounds into it.

GOOD: "The complexity of SLL(k) testing is exponential."

GOOD: "The complexity of SLL(k) testing is at least exponential."

GOOD: "There is an exponential lower bound on the complexity of SLL(k) testing."

GOOD: "The complexity of SLL(k) testing is in $\Omega(2^n)$."

BAD: "The lower bound of SLL(k) is exponential." \<--- Don't say this! There's more than one valid lower bound.

BAD: ""The complexity is at least $O(2^n)$." \<--- Don't say this! Big-O is an upper bound; it doesn't go with "at least".

---
Tags: complexity-theory, terminology, lower-bounds
---


# Question
Title: An advice to a self-learner of computational complexity
I'm a mathematics undergraduate student (going to start my third year very soon). I'm trying to teach myself computational complexity. Sadly, there are no courses provided in my university on the topic and there are no specialists on it (In fact, it seems that my university has no specialists in theoretical CS at all). So, I have no choice to learn the topic except via self-study. I've already gone through the first few chapters of ***Computational complexity: A modern approach*** \[ but I did not solve any of the exercises (except two or three in the first chapter exposing what are TM's and Halting problem) \]

I face some problems with the exercises of in the text:

1. one thing is that I feel that the kind of thinking needed in computational complexity is quite different than that of mathematics that I'm familiar with (There is an emphasize on algorithmic thinking etc and how to reduce problems to other problems and to make a TM simulating another TM etc) which is something I find difficult.

*Is there any way do you recommend to help me developing this level of maturity about algorithms, reductions etc?*
2. One reason of difficulty of "1" is that I don't know to what extent should I be rigorous? For example, when I'm doing a reduction or a simulation, it's possible that I can see intuitively that something is clear and can be done but the details would be very very tedious to actually carry out and hence I feel that I don't understand the thing very well. The point is that, I know that there must be a compromise between rigor and intuitive thinking. But since I've no guide nor an instructor, I don't know where this line should be.

*when should I carry out all the details if something somehow clear and when should I be satisfied with the intuition? It seems that there are much more details in computational complexity than is usually present in the math I know and hence, where the compromise should be?*
3. I wonder if there exists any source of exercises\problems that are quite easier than those provided in ***Computational complexity: A modern approach*** so that I can train myself with the basic notions\constructions etc before tackling more complicated exercises. Also, a source of (quite-detailed) proofs of the main theorems would be great since many theorems have only a sketch of the proof in the text.

For my background, I've learned basics of programming (I've trained for awhile in python, C and C++) but not much but I'm quite familiar with mathematics specially mathematical logic (up to completeness and Incompleteness theorems), advanced set theory (forcing), Algebra (linear, Abstract, universal algebra and some category theory) and basics of topology and reals analysis. I've taken a course on Discrete mathematics too (combinatorics + graph theory).

**I apologise if my question is off-topic but I know no better place to propose those question than here.**

# Answer
> 7 votes
My recommendation is to focus on two things: prerequisites, and practice.

Prerequisites: It's going to be harder to learn computational complexity without first having a good understanding of algorithms. At many schools, a class in algorithms is a prerequisite to the class on computational complexity. You mention you feel you may lack maturity in algorithms, and in your position, who wouldn't? It's a non-trivial subject that you haven't studied. So, my first piece of advice is: before spending too much time on computational complexity, first spend some time studying algorithms. There are many good algorithms textbooks and online courses (e.g., via Udacity, Coursera, or EdX). It might be helpful to spend some time learning that material. You don't need to learn every algorithm in the world, but try to get a feel for some common algorithmic techniques; designing reductions is basically designing an algorithm, so this knowledge will be helpful. Also, make especially sure you are comfortable with proofs of correctness for algorithms and asymptotic running time analysis.

Next, practice. No one starts out with a maturity with reductions. The way to get more comfortable with that is to practice -- do exercises until you either feel comfortable with the material, or the exercises uncover some gap in your understanding (which you can then go back and focus on learning more about). You probably can't learn the material without this kind of practice.

To help you practice, it may be helpful to look for an online course (a MOOC) on computational complexity. You can check Udacity, Coursera, or EdX.

How rigorous should you be? Rigorous enough that you are convinced that you could fill in all the details if you needed to (and that a fellow classmate at a similar level of studies could fill in all the details without thinking hard -- they'd agree filling in the details is tedious but straightforward and obvious).

# Answer
> 5 votes
Given that I'm the opposite (studying computer science/engineering, self studying math) I think I can shed some light on some topics.

I've recently taken an algorithms and complexity theory course that covered algorithms, formal languages, and complexity theory. I think all 3 will be very important if you want to really understand what you're doing. For example, if you don't understand big-O implications and how to analyze runtimes, you won't really understand what P and NP represent and it'll be harder to move into other complexity classes. If you don't understand TMs, automatas, etc., then you won't understand regular languages, CFGs, and what decidable and recursively enumerable languages represent. So my suggestions will stem from connections I've made to mathematics from computer science.

1. You've taken set theory and real analysis. You should be familiar with induction from most of your courses (a tool that was the most challenging part of algorithm analysis for many classmates) and recursion will most likely come naturally to you. When it comes to more abstract objects, while not directly related, I think a strong basis in abstract algebra (and anything further) will prove to be a huge advantage that you have. Groups, rings, etc., are algebraic objects that contain some structure and you have maps and morphisms between them. Turing Machines and automata are computational structures that contain some structure and rules and have transformations between them (Thompson's construction for regular expressions into NFAs, multi-tape TM's into a single tape TM). While general programming logic could be beneficial for understanding logic of TMs, category theory might help you out more.
2. I'm not sure what specifically you're asking, but if you can be rigorous, do it. There are some techniques used in mathematics that are used in many constructions (real analysis using epsilon delta proofs that build up to calculus from simple concepts) and there are techniques used in complexity theory (reductions from a problem to another, think of an injective map where you have to provide the map as opposed to proving it is injective).
3. This course (https://courses.engr.illinois.edu/cs374/lectures.html) provides lecture notes and slides and has great introductory reference materials. In no way does this cover everything, but it could be a great start for you. The lab work is pretty nice to look at and test your understanding, but often times it's more difficult than the required knowledge.

Lastly, your discrete maths will be of great help throughout all this. You'll see how important graph theory is in algorithm analysis and design as well as combinatorics for data structure analysis. Good luck and I hope you find what you're looking for!

# Answer
> 1 votes
I would suggest you (a) determine what prerequisite math you need, (b) stick to really understanding and going through the first 3-4 problems or so in each chapter, trust me even if those take long, you will get the hang of it then pretty quickly with future problems.

---
Tags: complexity-theory
---


# Question
Title: Reducing Zero-One Integer Linear Programming problem to SAT
I want to find a reduction from Zero-One Integer Linear Programming problem to Boolean Satisfiability problem (SAT), that is, to find a polynomial-time transformation $T$, such that: $$IP \leq\_P SAT$$ $$IP(in\_{IP}) = 1 \iff SAT(T(in\_{IP})) = 1$$ where $in\_{IP}$ is an input for the IP problem and $T(in\_{IP}) = in\_{SAT}$ is a boolean formula (input for the SAT problem).

First, I have considered a particular case for IP, where $$x\_1 +x\_2 + \cdots +x\_n \leq p$$ $$x\_i = 0 \ \text{or} \ x\_i = 1, \ \forall i =1..n, \ \forall p \geq0 $$ Translated into boolean language, the transformation will construct a formula where **at most** p variables must be set to true for the formula to be satisfiable.

Next, I've considered a concrete example, constructing the following ROBDD that allowed me to express the following inequality: $$x\_1 + x\_2 + x\_3 \leq 2$$ $\hskip 2.5in$

where continuous arrow means 1 and dotted arrow means 0. I have also invented the variabiles $x\_i\\\_$ that somehow *mirrors* the behaviour of $x\_i$ sub-component (i.e. swaps routes).

Now, is there a way I can formalize this whole process, that is, express the concept of **at most** in boolean algebra language? I think this is the key to find the actual transformation.

# Answer
The existence of such a reduction follows immediately from the Cook-Levin theorem, which guarantees that you can reduce *any* problem in NP to SAT and describes explicitly one way to do it. Just work through the steps of the proof of the theorem (which can be found in any textbook) and you'll obtain a valid reduction from 0-1 ILP to SAT.
> 6 votes

# Answer
There are two variants to perform the encoding. I am assuming that you want the SAT instance in Conjunctive Normal form, as otherwise your ROBDD can be mapped pretty directly to a Boolean formula of size (but not length) linear in the number of variables.

In **variant 1**, we do not want to introduce additional variables. Essentially, we want to add clauses that rule out all paths in the ROBBD that lead to the "0" node. So if $x\_1 + x\_2 + x\_3 \leq 2$, this would be only one clause, namely $\neg x\_1 \vee \neg x\_2 \vee \neg x\_3$. For translating $x\_1 + x\_2 + x\_3 \leq 1$, there are four different paths in the ROBBD to the "0" node. Encoding the paths yields $\neg x\_1 \vee \neg x\_2 \vee \neg x\_3$, $\neg x\_1 \vee \neg x\_2 \vee x\_3$, $x\_1 \vee \neg x\_2 \vee \neg x\_3$ as clauses, which can be simplified to $\neg x\_1 \vee \neg x\_2$, $\neg x\_2 \vee \neg x\_3$, $\neg x\_1 \vee x\_3$. Note that the number of clauses necessary for this encoding can be exponential in the number of variables employed in the inequality, so this encoding is not always suitable.

In **variant 2**, we introduce additional variables to the SAT problem to help us with the encoding. For example, we can introduce for the every ROBDD node a SAT variable and then encode which path through the ROBDD the assignment to $x\_1, x\_2, x\_3$ takes. Example:

* $v\_1$
* $\neg v\_1 \vee \neg x\_1 \vee v\_2$
* $\neg v\_1 \vee x\_1 \vee v\_T$
* $\neg v\_2 \vee \neg x\_2 \vee v\_3$
* $\neg v\_2 \vee x\_2 \vee v\_T$
* $\neg v\_3 \vee \neg x\_3 \vee v\_F$
* $\neg v\_3 \vee x\_3 \vee v\_T$
* $v\_T$
* $\neg v\_F$

The added $v$ variables represent which node in the ROBDD is reached. Note that this example is not built after your ROBDD, as it does not represent $x\_1 + x\_2 + x\_3 \leq 2$, as it maps $x\_1 = 0$, $x\_2 = 1$, $x\_3 = 0$ to $0$.

The nice property of variant 2 above is that the encoding is only linear in the size of the ROBDD, which in turn is at most quadratic in the number of variables employed in the inequality. But note that there are also many other possible encodings of the linear inequality into SAT. The paper \`\`PBLib – A Library for Encoding Pseudo-Boolean Constraints into CNF'' contains some pointers.
> 5 votes

---
Tags: complexity-theory, np-complete, reductions, satisfiability, integer-programming
---


# Question
Title: Minimum number of sets of unreachable vertices for directed acyclic graph (DAG)
I have a DAG with vertices $V$ and edges $E$. If $v,w \in V$ are vertices such that $v$ is not reachable from $w$ and $w$ is not reachable from $v$, I will say that $\langle v,w \rangle$ is an *unreachable pair*.

I want to implement an efficient algorithm which takes this DAG as input, and produces as output a list of sets of pvertices such that:

1. For each unreachable pair of vertices $\langle v,w \rangle$, at least one of the output sets contains both $v$ and $w$,
2. Every pair of vertices $v,w$ that are contained in the same output set must be an unreachable pair, and
3. The number of output sets must be the minimum possible.

Is there a polynomial-time algorithm for this problem?

---

As an example, we have the following DAG with topologically ordered vertices `A,B,C,D,E`:

```
A is connected to [D, E]
B is connected to [D, E]
C is connected to [E]
D is connected to []
E is connected to []

```

which means that we have the following unreachable vertex pairs:

```
1. <A, B>
2. <A, C>
3. <B, C>
4. <C, D>
5. <D, E>

```

The expected output is composed of the following three vertex sets:

```
1. {A, B, C}
2. {C, D}
3. {D, E}

```

The output was not {A,B} {A,C} {B,C} {C,D} {D,E} because the minimum number of possible output sets is 3 instead of 5 as given above. Otherwise it would satisfy the first two conditions, but not the third condition.

As another example, consider the same DAG vertex set V but where the edge set E is empty. Since all vertex pairs would be unreachable, the expected output is the vertex set V itself.

# Answer
The problem is fixed-parameter tractable, where the parameter is the number of output sets.

Define an undirected graph $G'$ with an edge $(v,w)$ for each unreachable pair of vertices in the original graph. Now you want to find a minimal edge clique cover of $G'$. The minimal edge clique cover problem is fixed-parameter tractable, where the parameter is the number of cliques.

I don't know if there is a polynomial-time algorithm. The minimal edge clique cover problem is NP-complete for general graphs. I don't know if $G'$ has any special properties that makes the minimal edge clique cover problem easy on it. (It's not necessarily chordal, unfortunately.)
> 1 votes

---
Tags: algorithms, graphs, sets, dag
---


# Question
Title: Distance query in trees with integer edge weights (Constant time, linear space)
Consider an unrooted tree with integer edge weights. I'm looking for a linear space data structure which allows for constant time distance queries (finding the distance, i.e. the sum of edge weights, between any two vertices).

Is this possible? If yes, how? I have an idea that it should be possible using some Lowest-Common-Ancestor or Range-Minimum-Query approach.

# Answer
Pick an arbitrary node to be the root. Store in each node its depth (distance from the root). Also, build a least-common ancestor data structure so you can answer least-common ancestor queries in constant time.

Given two vertices $u,v$, compute their least common ancestor, $a$. Now the shortest path from $u$ to $v$ goes up from $u$ to $a$, then down to $v$. You can compute the length of this path as

$$(\text{depth}(u)-\text{depth}(a)) + (\text{depth}(v) - \text{depth}(a)).$$

That's the distance from $u$ to $v$. Total running time is $O(1)$ time per query. There exist LCA data structures that use only linear space.
> 2 votes

---
Tags: graphs, data-structures, trees
---