# Question
Title: is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation
I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance!

> Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( usually $N$ is a large number, $K$ is a small number). Each row of the matrix contains distinct values, but each column may contain duplicate values. For $i = 1, 2, \cdots, K$, let $m\_i$ denote the count of distinct values at $i$-th column and define $\rho := min(m\_1, m\_2, \cdots, m\_K)$. If we can swap any two numbers within each row, how to minimize $\rho$ provided you can perform any number of the given operations(swaps)?
>
> Can this problem be NP-complete in terms of $N$??

For example: in a $4\times3$ matrix $$ \begin{matrix} 1&2 & 3\\ 3&4& 5\\ 4&5& 7\\ 6&7& 8\\ \end{matrix} $$ Since only swaps within a row are allowed, we can swap 1 and 2 in the first row, but cannot swap 1 in the first row with 4 in the second row. I think after performing a few swaps, one optimal solution we can get is $$ \begin{matrix} 1&2 & 3\\ 4&5& 3\\ 4&5& 7\\ 6&8& 7\\ \end{matrix} $$ where $m\_1 = 3, m\_2=3, m\_3 = 2$,
Hence the minimum count of distinct values of all columns is $\rho = 2$.

# Answer
> 3 votes
The first thing we have to do is define a decision version of your problem, like for example:

Is it possible to swap the elements inside the rows of the matrix so that in at least one column the number of distinct elements is less or equal than $\rho$?

Well, the first thing to take into account is that this problem is just asking if we can swap elements inside the rows in order to find a column where the number of distinct elements is less or equal than $\rho$.

We are going to reduce the decision version of 3HITTING SET to the decision version of your problem. 3HITTING SET is an np-complete variant of minimum hitting set where all subsets have only three elements. Hitting set is like the inverse of set cover. In minimum set cover you cover members of the universe with subsets and in miminum hitting set you cover subsets with members of the universe. That means that if an element appears in a subset, that subset is covered by the element. The objective is to find the minimum number of elements inside the universe that are enough to cover all subsets.

A decision version of 3HITTING SET will be:

Is it possible to cover all subsets with at most $\rho$ elements of the universe?

Now with the reduction:

We simply convert each subset of the hitting set problem into a row of your problem. That is we create a matrix $A$ .Then, for each subset $i$ that belongs to the hitting set instance, we create a row $i$ inside the matrix $A$. And then for each element $j$ that belongs to the universe in the hitting set instance being reduced, we create a number inside the matrix, this number will be inside row $A\_i$ if the element $j$ that belong to the universe appears inside the subset $i$ in the hitting set instance.

If there is a hitting set of size $\rho$, then we will have a matrix where we can form a column by swapping with at most $\rho$ distinct elements.

The reason for this is that if we can cover the sets of the hitting set instance with $\rho$ elements then we can form a column with $\rho$ or less distinct elements inside the matrix by picking the numbers that were mapped to elements of the universe in the hitting set instance and swapping them inside the rows of the matrix so that they are all in the same column.

For the other direction, that is, for the cases in which there is no minimum hitting set instance with at most $\rho$ distinct elements we have to show that those cases are converted in our reduction into matrices where we can´t form a column with at most $\rho$ elements by swapping numbers inside rows.

If on those instances we could, by swapping numbers inside rows, create a column with at most $\rho$ elements inside the matrix; that would mean that there exists $\rho$ elements that can cover the subsets in the hitting set instance. This is a contradiction

The reason is that we have mapped every element of the universe in the hitting set instance to a different number inside the matrix and also we have mapped every subset into a different row inside the matrix. So if we could form a column with at most $\rho$ distinct elements by swapping elements inside the rows, that will mean that there is at least one of those numbers inside each row. Because each subset of the hitting set instance was mapped to a different row and each element of the universe is mapped to a different number inside the matrix, that will mean that we can cover the subsets with those $\rho$ elements in the hitting set instance.

---
Tags: algorithms, combinatorics, matrices
---


title: Common subset sum fast algorithm

text:
# Question
Title: Common subset sum fast algorithm
Suppose of I two sets of $n$ integers bounded in $\[-B,B\]$. The integers are $$a\_1,\dots,a\_n$$ $$b\_1,\dots,b\_n$$

I want to find if there is a common subset $I\subseteq\\{1,\dots,n\\}$ such that $$\sum\_{i\in I}a\_i=0$$$$\sum\_{i\in I}b\_i=0$$

This problem is $NP$-complete.

Is there a pseudo polynomial time algorithm with complexity for this problem like the regular subset sum problem on bounded integers which has an $O(B^2)$ algorithm (https://en.wikipedia.org/wiki/Subset\_sum\_problem#Pseudo-polynomial\_time\_dynamic\_programming\_solution)?

# Answer
Yes, we shall use dynamic programming and extend our subset-sum algorithm here.

* Let $R(i, \ s, \ t)$ be **true** iff there exists a subset $K \in \\{1, ... i\\}$ such that $$\sum\_{i \in K} a\_i = s \quad and \quad\sum\_{i \in K} b\_i = t.$$

Which subproblem would then give us the result we need? $R(n, 0, 0)$!

Now, let's find a recursive relation for our subproblem in terms of smaller subproblems: $$R(i, \ s, \ t) := \[(a\_i==s) \wedge (b\_i==t)\] \\\vee R(i-1, \ s, \ t)\\\vee\ R(i-1, \ s-a\_i, \ t-b\_i) $$

where, $\vee$ is the OR operator and $\wedge$ is the AND operator.

This relation works on the inclusion-exclusion principle - either we include the $i$th index in our subset $K$ or not. But the caveat here is that if we include the $i$th index, we must include both $a\_i$ and $b\_i$.

* If we do **not** include the $i$th index, $R(i, \ s, \ t)$ reduces simply to $R(i-1, \ s, \ t).$
* If we **do** include the $i$th index, either ($a\_i$ should be $s$) AND ($b\_i$ should be t). Or, we must have some common subset of the two sets summing to $s-a\_i$ and $t-b\_i$ respectively i.e. $R(i-1, \ s-a\_i, \ t-b\_i)$ should be true.

For the sake of completeness, the base cases are $R(1, \ s, \ t) := (a\_1 ==s) \wedge (b\_1==t)$.

**Edit**:The runtime of the algorithm then is $O(n^3{B^2})$ (Why?), which is pseudo-polynomial too.
> 1 votes

---
Tags: algorithms, pseudo-polynomial
---


title: Branch and Bound - Transform a into b

text:
# Question
Title: Branch and Bound - Transform a into b
I'm trying to design an algorithm which will accept two natural numbers: a and b. Its purpose is to get b from a by making the following operations: \*3 and /2. For example, if a = 10 and b = 7, then:

```
10/2*3/2 = 7

```

I decided to use branch and bound, since I believe there's no better suitable algorithm for this.

My program works, but I'm having really trouble finding a heuristic.

What could it be?

Thank you.

# Answer
I don't know of any algorithm that will work for all $a,b$, because of the possibility that you might have to use an intermediate value that is extremely large, and I'm not aware of any reasonable bound on how large of an intermediate value you need to contemplate.

However, here's one heuristic. Suppose we only consider sequences where no intermediate value exceeds some constant $K$. Then you can use dynamic programming to determine whether it's possible to go from $a$ to $b$, without ever exceeding $K$. You build an array $A\[1..K\]$ where $A\[i\]=1$ means that it's possible to reach $i$ from $a$, and fill it in via a fixed point computation, as follows:

1. Set $A\[a\]=1$ and $A\[i\]=0$ for all $i \ne a$.
2. Repeatedly do the following, until you do an entire iteration without changing the array:
    * For each $i := 1,2,\dots,K/3$, if $A\[i\]=1$, set $A\[3i\] := 1$.
    * For each $i := 3,4,\dots,K$, if $A\[i\]=1$, set $A\[\lfloor i/2 \rfloor\] := 1$.

Finally, if $A\[b\]=1$, you know it's possible to go from $a$ to $b$. (If $A\[b\]=0$, you can conclude nothing; maybe there's a way to get from $a$ to $b$ by going through some intermediate value larger than $K$.)
> 2 votes

---
Tags: heuristics, branch-and-bound
---


# Question
Title: Testing whether an arbitrary proof is circular?
I was thinking about proofs and ran into an interesting observation. So proofs are equivalent to programs via the Curry-Howard Isomorphism, and circular proofs correspond to infinite recursion. But we know from the halting problem that in general testing whether an arbitrary program recurses forever is undecidable. By Curry-Howard, does that mean there is no "proof checker" that can determine if a proof uses circular reasoning?

I've always thought that proofs are supposed to be composed of easily-checkable steps (which correspond to applications of inference rules), and checking all the steps gives you confidence that the conclusion follows. But now I'm wondering: maybe it is actually impossible to write such a proof checker, because there is no way for it to get around the halting problem and detect circular reasoning?

# Answer
The vast majority of proof systems don't allow for infinite, circular proofs, but they do so by making their langauges non-Turing complete.

In a normal functional language, the only way to make a program go on forever is with recursion, and in terms of theory, usually we look at recursion as the $Y$ combinator, a program of type $\forall a \ldotp (a \to a) \to a$: that is, it takes a function which makes calls to some other "self" argument, and turns it into a single recursive function.

Now, apply the Curry-Howard isomorphism to this: we now have a proof that, for any proposition $a$, if $a$ implies itself, then we can prove $a$. We can prove anything this way!

The key here is that the Y-combinator is built-in to a language, it's taken as an axiom. So if you want it not to cause you problems, just get rid of it as an axiom!

Most formal proof systems, because of this, require your recursion to be well founded. They only accept functions that they can prove will halt. And as a result, they reject some programs that do halt, but which they can't prove it for.

Coq does this in a fairly limited way: it just requires that any recursive functions have an argument where any recursive calls only use strictly smaller versions of that argument. Agda does something similar, but with a little more fancy checking to accept a few more programs.
> 15 votes

---
Tags: logic, curry-howard
---


# Question
Title: Distributed systems according to Lamport?
I need some clarification over the following quotation of Leslie Lamport:

> A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system.

I see how a distributed system can be modeled as the product of several particular sequential state machines.

I understand that by totally ordering input requests, one can duplicate a given sequential state machine over several computers, and make sure that all input requests are processed in the same order at every computer, and thus ensuring that the individual local states are coherent.

What I don't understand is how this mechanism is sufficient to implement ANY distributed system. At least it's sufficient to duplicate a sequential state machine, but isn't that a very particular case of a distributed system?

# Answer
> 1 votes
My interpretation of this quote is that if we consider the whole distributed system as a black box containing multiple local processors, then when we send input requests to this box, the whole box moves to another state even though we don't know what that next state is (particularly in non-deterministic state machines), but we are sure that there's no inconsistent interpretation within the box.

Actually input requests could be thought of as an external node that does atomic broadcast to all internal nodes (within the box). This type of broadcast ensures us that all internal nodes receive messages in the same order, so all local state machines move to their next states. If we define state of the whole system as a set of all internal local states, so whenever we receive an atomic broadcast (i.e. input request), our system's state moves to a next state depending on the order of messages that all internal nodes agree on. Hence, each different order leads us to a non-deterministic destination (the next state) in the state machine of the whole system.

Therefore, total ordering is sufficient to model a distributed state machine. However in some applications some more properties might be needed, for instance, FIFO ordering, causal ordering, etc.

# Answer
> 0 votes
I don't think that quote trying to claim that this is necessarily the only possible definition of distributed system. It's one way to think about distributed systems that will often apply. For instance, if there's a single interface for interacting with the distributed system (so that the inputs and outputs can be totally ordered, as described in the quotation), then from an external perspective we can think of the entire system as implementing a single state machine.

---

A side remark. I don't think it's saying: given a sequential state machine, we can implement it in a distributed system (by replication, consensus protocols, etc.). Instead, I think it's saying the following: given a distributed system, its externally observable behavior could be described by a sequential state machine (e.g., the distributed system could be replaced by a non-distributed, sequential system that has the same input-output behavior).

---
Tags: distributed-systems
---


# Question
Title: How to Modify SAT Solvers to Produce Resolution Refutations for Unsatisfiable Instances?
In recent SAT competitions, there is a Certified UNSAT track. The problem instances are all unsatisfiable and the solvers are asked to produce certificates for unsatisfiability. One way is to produce a resolution refutation for the set of clauses in a problem instance. How can a SAT solver, say MiniSAT, be modified to do this? Can this be done for every solver? I searched the Internet and found little information. A reference is good for me.

# Answer
If you know something about CDCL conflict clause generation, you will know that they are produced by resolution *per se*. For example, on page 137 of *Handbook of Satisfiability*, clause learning is done by the following procedure: $$\omega\_L^{d,i}=\begin{cases}\alpha(\kappa)&{\rm if\ }i=0\\ \omega\_L^{d,i-1}\odot\alpha(l)&{\rm if\ }i\ne0\land\xi(\omega\_L^{d,i-1},l,d)=1\\ \omega\_L^{d,i-1}&{\rm if\ }i\ne0\land\forall\_l\xi(\omega\_L^{d,i-1},l,d)=0 \end{cases}$$ Here, $\alpha(v)$ is the antecedent of $v$. The first line specifies the base case. The recursion will ensue following the second line. The third line signals a fixed point and the process halts. Note in the second line, $\odot$ signifies resolution.

So just print the generation process and you will get a resolution refutation of the unsatisfiable formula.
> 1 votes

# Answer
A clause-learning SAT solver can be described approximately as follows. There is a stash of learned clauses, which starts empty. We run a recursive procedure, which at each point in time, first checks whether the current assignment (initially empty) contradicts an axiom or something in the stash. If so, there is no need to explore this branch. Otherwise, it picks a variable, and tries both assignment recursively. When a recursive call corresponding to a partial assignment $\alpha$ returns, we learn the clause $\lnot \alpha$. At any given point in time we are allowed to forget clauses. (It's important for the proof that each clause is learned, even if we forget it later on).

We now take the transcript of the algorithm and consider the clauses in the order in which they are learned. We prove that whenever a clause $c$ is learned, it can be derived using the rules of resolution from existing clauses or from axioms; in particular, at the very end we derive contradiction.

We allow the weakening rule in the refutation we construct; we can always get rid of weakening later on without increasing the refutation length (exercise).

There are three cases to consider. If the clause $c$ was learned because the corresponding assignment contradicted an axiom $c'$ or a clause in the stash $c'$, then $c$ is a weakening of $c'$. The interesting case is when $c = \lnot \alpha$ was learned since both assignment to some variable $x$ failed to produce a satisfying assignment. These assignments correspond to the learned clauses $c \lor x$ and $c \lor \lnot x$, from which $c$ follows by resolution.

Note that if we never use clauses in the stash then the resulting refutation is tree-like (every clause is used once), assuming we state each axiom whenever it's needed (rather than once and for all). Also, in any case the size (number of lines) of the refutation is the same as the number of recursive calls.
> 5 votes

# Answer
The simplest method of modifying a typical DPLL-based CDCL solver is to have it output every clause it learned while deciding a formula is unsatisfiable. Such a list of clauses constitutes a RUP proof, which can be used to either construct a traditional resolution-based proof of unsatisfiability or show unsatisfiability directly using a somewhat different verification scheme. See "Verification of Proofs of Unsatisfiability for CNF Formulas" and "Verifying RUP Proofs of Propositional Unsatisfiability" for the details.
> 3 votes

# Answer
Not every solver can be thus modified, and people are searching for new solvers that cannot produce resolution refutations. (Resolution is slow and we want fast solvers.)

But CDCL solvers can p-simulate general resolution. That means they can produce resolution refutations that are only polynomially larger than general resolution. The method is written in Pipatsrisawat and Darwiche's On the power of clause-learning SAT solvers as resolution engines.

But that is not a good answer, because we want to show SAT solvers are slow, instead of how efficient they are. One way is to show general resolution p-simulates CDCL solvers. But people are too happy proving how good SAT solvers are to consider the other direction.

I don't know how to answer my own question. That's why I seem to turn this to a discussion forum. But that's why I'm asking in the first place.

Those who know why "CDCL solvers correspond to general resolution" please stand up and explain why general resolution is as good as CDCL SAT solvers!
> -2 votes

---
Tags: algorithms, sat-solvers
---


# Question
Title: defining the operational semantics of a concurrent language
As big-step operational semantics is about evaluating an expression to a final value, can we state that for defining a concurrent language one needs small-step semantics, as concurrent programs need not result in a value?

# Answer
> 3 votes
Coinductive Big-Step Semantics for Concurrency by Tarmo Uustalu writes:

> Second, contrary to what is so often stated, concurrency is not inherently small-step, or at least not more inherently than any kind of effect produced incrementally during a program’s run (e.g., interactive output). Big-step semantics for concurrency can be built by borrowing the suitable denotational machinery, except that we do not want to use domains and fixpoints to deal with partiality, but coinductively defined sets and corecursion.

So the answer is that it is stated throughout the literature, but it is not true.

---
Tags: concurrency, operational-semantics
---


# Question
Title: What makes an operational semantics good?
Some papers define an operational semantics of a programming language. That is nice, but what makes such a semantics fit for the purpose?

An idea is to have a progress theorem, i.e. well-formed expression is either a value or a reduction can take place

another is type preservation, that an reduction preserves the type of an expression.

What else is a test for the adequateness of a semantics? What should I prove about it?

# Answer
I think you have it a bit backwards: proving type preservation is a good property of the *type system* with respect to the operational semantics, rather than the opposite.

Alternately: the whole point of a programing language is the ability to use it to perform some computational task. Because of this, the operational semantics is one of the *requirements* of having a programing language. The only real "fitness test" you need is

> Can I write the programs I want using this language?

You might then want to prove that say, a *compiler* is correctly implemented by showing that the computational behavior of (well-behaved) code is equivalent in some sense to the operational semantics, but again, here I would take the semantics themselves to be primal rather than the opposite.

In certain fields of mathematics, notably in the area which studies the propositions-as-types correspondence, one might be more interested in the static semantics (the type system) and have the operational semantics more as an afterthought, where progress, preservation and termination have consequences on the type system as a logic (typically, that the logic is consistent).

But again, usually the operational semantics is primitive, and it is well-defined exactly when it enables the programmer to write the program she wishes to write (and possibly prevents some "bad" programs).
> 4 votes

---
Tags: operational-semantics
---


# Question
Title: How to compute the sum of this series involving golden ratio, efficiently?
**Definitions**

1. Let $\tau$ be a function on natural numbers defined as $\tau(n)=\lceil n\*\phi^2\rceil$ where $n$ is some natural number and $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. This series can also be looked up here : A004957, with first few terms being $3,6,8,11,14...$ .
2. Let $t$ be the largest natural number such that $\tau(t) \le 10^{16}$.
3. Let $S\_i$ for $1 \le i \le t$ be defined as $S\_i=-(10^{16}-\tau(i)+1)\*i+ 2\*\sum\_{j=\tau(i)}^{j=10^{16}} j $.

**Problem**
How can I compute the sum $(S\_1+S\_2+...S\_t)$ % $7^{10}$ efficiently ? I tried thinking by matrix exponentiation, but can't come up with a method due to the form of the $\tau$ function.

PS: This question is my way of trying to solve the problem : stone game II.

# Answer
> 6 votes
As D.W. pointed out there should be some kind of recurrence involving the $\tau$ function. Turn's out there is, let us again look at the $\tau$ function series, the first few terms are

$$3,6,8,11,14,16,19,21.... \\; \\;(1)$$

Now let us look at the difference between consecutive terms of the series,

$$3,2,3,3,2,3,2..... \\; \\; (2)$$

Turns out sequence $(2)$ is the infinite fibonacci word ( again some sort of strong correspondence between golden ratio and fibonacci sequences ) made up of $2's$ and $3's$. This fibonacci sequence is as follows, the first two terms are

$a\_0 = 3$ , and $a\_1=3,2$ and for $n\ge 2$, $a\_n=a\_{n-1}.a\_{n-2}$, where "." represents string concatenation. First few terms of the fibonacci word are

$$a\_0=3$$ $$a\_1=3,2$$ $$a\_2=3,2,3$$ $$a\_3=3,2,3,3,2$$

and so on. With this construction the summation I mentioned can be calculated very quickly. Also I did not make any use of the fact that modulo was taken by $7^{10}$. It would be interesting if this fact could be used somehow as D.W. suggested.

PS: I solved the question using the same formula in my question. Above I provide only a hint as coming from a non-math background I found the question really interesting and won't ruin it for others.

---
Tags: time-complexity, number-theory
---


# Question
Title: How can I study the nature of the structure of evaluation of function in lambda calculus?
I am specifically focusing on lambda calculus, following this paper: A Tutorial Introduction to the Lambda Calculus.

Suppose we have three functions that represent the natural numbers 0 and 1, and a successor function:

$\lambda sz.z = 0$

$\lambda sz.s(z) = 1$

$\lambda wyx.y(wyx) = succ$

Suppose I were to evaluate $succ\ succ\ 1$. As I evaluate this expression, it is becoming clear to me that it's not 3 as I might naively expect, but I do not truly grasp "why." Even as I go through the motions of evaluating the expression, I do not understand the nature of the turn of events and why certain expressions produce a certain result due to their structure and construction.

A question I might ask would be something like, why does $succ$ have that form, and is there an alternative form for $succ$ that produces the same result? If it is unique, what makes it special? I don't know how to answer these questions well yet, so I am seeking guidance.

Is there a method by which I can better visualize or understand the evaluation of expressions and how it affects the "class" of their output? I am very new to lambda calculus, so please excuse me.

**Edit:** I think I understand the rules for evaluation of lambda calculus (substitution, prevention of name collisions, etc.), but I have a hard time understanding the arbitrary rules by which one can construct lambda calculus' equivalent forms for the natural numbers, the successor functions, and the addition and multiplication functions. It's how these parallels to these concepts were mapped over to lambda calculus that I am interested in.

For example, why are the functions for "choose second," "false," and "discard next argument," and "0" have the same form and thus equivalent? There exists systems in which applying the zero function to a list of object does not result in returning a list with the front-most argument removed. Even if it is a convention, is there a reason why it is structured as such?

For example, why is does the successor function work? One can say that it was discovered through trial and error, but this makes for poor understanding of the nature of a concept besides "it is so" and "it works." I hope this makes sense.

# Answer
I'll try addressing only some of the questions.

Church numerals are defined to be functions (*abstractions* in $\lambda$-calculus speech) that take two arguments: a base argument $z$ (stands for zero), and a "successor" function $s$ which will be *repeatedly* applied to the base $z$. The number of times $n$ we apply $s$ corresponds to some natural number $n$.

The successor function $\mathsf{succ}$ takes a Church numeral corresponding to some $n \in \mathbb{N}$ (the numeral's canonical form is $\lambda sz. s^nz$), and returns a Church numeral corresponding to $n+1$, i.e. some term that *behaves* like $\lambda sz. s^{n+1}z$.

Notes:

* $s^n z$ means $s (s (s (... s z))...)$, where $s$ applied $n$ times to $z$;
* two abstractions are behaviorally equivalent if applied to the same arguments they yield the same result.

Let's obtain a $\lambda$-term representing $\mathsf{succ}$. In what follows I'm using Church numerals and corresponding natural numbers interchangeably, I hope that it won't cause confusion, since the current domain can be derived from the context.

1. $\mathsf{succ}$ is an abstraction that takes a Church numeral $n$, so $\mathsf{succ} = \lambda n. \textsf{\<...\>}$
2. $\mathsf{succ}$ returns a Church numeral, which must take 2 arguments, that's why $\mathsf{succ} = \lambda n. (\lambda sz. \textsf{\<...\>})$
3. After supplying some $s$ and $z$ to $(\mathsf{succ}\ n)$ we must have $s$ applied $n+1$ times to $z$. Notice that the Church numeral $n$ allows us to easily get $s$ applied $n$ times: we just apply $n$ to $s$ and $z$: $(n\ s\ z) = s^n z$. Then, using the fact $s^{n+1} z = s (s^n z)$, we get $s^{n+1} z = s (n\ s\ z)$. Finally, $\mathsf{succ} = \lambda n. (\lambda sz. s (n\ s\ z))$ or, sweetening with some more syntactic sugar, $\mathsf{succ} = \lambda nsz. s (n\ s\ z)$.

The term we've got for the successor function is not unique, one can use any form of $\mathsf{succ}$ as long as it fulfills its role: make "the next" Church numeral out of the current one. For instance, the following is a valid term for $\mathsf{succ}$ too: $\lambda nsz. n s (s z)$, and it can be obtained using the fact $s^{n+1} z = s^n (s z)$.

In fact, there are infinitely many syntactically different $\lambda$-terms for the successor function. We can invent many different (and silly) ways of "implementing" $\mathsf{succ}$: make a Church pair $(\lambda nsz. s (n\ s\ z), \text{\<any-term\>})$ and take its first component, i.e. $$ \mathsf{succ} = \mathsf{fst}\ (\mathsf{pair}\ (\lambda nsz. s (n\ s\ z))\ \text{\<any-term\>}), $$ or add $x+1$ to a number and subtract $x$, i.e. $$ \mathsf{succ} = \lambda n. \mathsf{minus}\ ((\mathsf{plus}\ n\ \mathsf{(x+1)})\ \mathsf{x}) $$

---

Now, let's address the $\mathsf{succ}\ (\mathsf{succ}\ 1)$ issue (I'm using the unrestricted evaluation strategy here): $$ \begin{array} \mathsf{succ}\ (\mathsf{succ}\ \mathsf{one}) &= \quad \text{(by definitions of succ and one)} \\ \mathsf{succ}\ ((\lambda nsz. s (n s z))\ (\lambda sz.s z)) &\to\_{\beta} \\ \mathsf{succ}\ (\lambda sz. s ((\lambda sz.s z) s z)) &\to\_{\beta}^{\*} \\ \mathsf{succ}\ (\lambda sz. s (s z)) &= \quad \text{(by definition of succ)} \\ (\lambda nsz. s (n s z))\ (\lambda sz. s (s z)) &\to\_{\beta} \\ (\lambda sz. s ((\lambda sz. s (s z))\ s z)) &\to\_{\beta}^{\*} \\ (\lambda sz. s (s (s z))) \end{array} $$ We've got a $\lambda$-term which clearly represents the number $3$ as was expected. If you try using $\lambda nsz. n s (s z)$ as the successor function you'll get the same result.

Under more restricted reduction strategy, viz. the call-by-value strategy, we sometimes get a term which doesn't look like a Church numeral at all, but *behaves* like one. A classical example is $$ \begin{array} \mathsf{succ}\ 1 &= \\ (\lambda nsz. s (n s z)) (\lambda sz. s z) &\to\_{\beta} \\ \lambda sz. s ((\lambda sz. s z) s z) \end{array} $$

The result is behaviorally equivalent to $\lambda sz. s (s z)$.

---

Now I'm going to show that $(\mathsf{succ}\ \mathsf{succ})\ N$ is equivalent to Church numeral corresponding to $N(N+1)$. Then somewhat unintuitive term $(\mathsf{succ}\ \mathsf{succ})\ 1$ indeed evaluates to $2$.

$$\begin{array} \mathsf{succ}\ \mathsf{succ}\ N &= &\text{unfold the 1st succ}\\ (\lambda nsz. s (n s z))\ \mathsf{succ}\ N &\to\_{\beta} \\ (\lambda sz. s (\mathsf{succ}\ s\ z))\ N &\to\_{\beta} \\ \lambda z. N\ (\mathsf{succ}\ N\ z) &\to\_{\beta}^{\*} &\text{(apply succ to N)}\\ \lambda z. N\ (\\{N+1\\}\ z) &=\_{\alpha} &\text{(rename z → s)} \\ \lambda s. N\ (\\{N+1\\}\ s) &= &\text{unfold {N+1}} \\ \lambda s. N\ ((\lambda tz'. t^{N+1}\ z')\ s) &\to\_{\beta} \\ \lambda s. N\ (\lambda z'. s^{N+1}\ z') &= &\text{(unfold N)} \\ \lambda s. (\lambda tz. t^{N}\ z)\ (\lambda z'. s^{N+1}\ z') &\to\_{\beta} \\ \lambda s. (\lambda z. (\lambda z'. s^{N+1}\ z')^{N}\ z) &= &\text{(syntactic sugar)} \\ \lambda sz. (\lambda z'. s^{N+1}\ z')^{N}\ z &\to\_{\eta} &\text{(η-reduction)} \\ \lambda sz. (s^{N+1})^{N}\ z &= \\ \lambda sz. s^{N(N+1)}\ z &= \\ N(N+1) \end{array}$$
> 4 votes

---
Tags: lambda-calculus, church-numerals
---


# Question
Title: Permutation on matrix to fill main diagonal with non-zero values
I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled with non-zero values. My matrices represent a set of linear equations and there is no problem to use permutations between rows and columns of my matrix to get a zero-less diagonal.

I do know that the matrix is non-singular so such a permutation must exist (otherwise the determinant would be null), however I searched on the internet and wasn't able to find anything relevant.

Here is an example were `0` denotes an null value and `1` any non-zero value. I numerated the rows, the permutation only changes the rows:

```
(row)    (matrix)        (matrix, blanks are zeros)

original:
01    1000011110000000    |1    1111       |
02    0100010001110000    | 1   1   111    |
03    0010001001001100    |  1   1  1  11  |
04    0001000100101010    |   1   1  1 1 1 |
05    0000100010010110    |    1   1  1 11 |
06    0000000000001110    |            111 |
07    0000000000110010    |          11  1 |
08    0000000001010100    |         1 1 1  |
09    0000000110000010    |       11     1 |
10    0000001010000100    |      1 1    1  |
11    0000010010010000    |     1  1  1    |
12    0001100000000010    |   11         1 |
13    0010100000000100    |  1 1        1  |
14    0100100000010000    | 1  1      1    |
15    1000100010000000    |1   1   1       |
16    1000000000000001    |1              1|

permutated:
01    1000011110000000    |1    1111       |
02    0100010001110000    | 1   1   111    |
03    0010001001001100    |  1   1  1  11  |
04    0001000100101010    |   1   1  1 1 1 |
05    0000100010010110    |    1   1  1 11 |
11    0000010010010000    |     1  1  1    |
10    0000001010000100    |      1 1    1  |
09    0000000110000010    |       11     1 |
15    1000100010000000    |1   1   1       |
08    0000000001010100    |         1 1 1  |
07    0000000000110010    |          11  1 |
14    0100100000010000    | 1  1      1    |
06    0000000000001110    |            111 |
13    0010100000000100    |  1 1        1  |
12    0001100000000010    |   11         1 |
16    1000000000000001    |1              1|

```

Is there a smart way to perform those row/column permutations in order to get a main diagonal without zeros ? I am almost certain that there is a way to express this problem as a path-finding problem (visit all the columns once and only if the current line of a column is a non-zero value) but wasn't very successful.

# Answer
You can use bipartite matching for that.

Nodes corresponding to rows in one set, nodes corresponding to columns in the other set. A row has an edge to every column in which it has a 1. If the maximum matching has size n, every row is matched up with a corresponding column and the matching gives the order. The index of the column that a row is matched up with will be its new position.
> 2 votes

---
Tags: graphs, matrices, linear-algebra, permutations, sparse-matrices
---


title: operator precendence grammar

text:
# Question
Title: operator precendence grammar
According to this post https://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel with operator. Actually i dont understand the rules which tells how to build such table. For example take last production `term -> '(' expr ')'` do we use rule `terminal nonterminal` because of `( expr` or do we use rule `nonterminal terminal` because of `expr )` or do we use rule `terminal nonterminal terminal` shoudl we divide production or treat as whole? Then is there any other rule applicable in example from link then `terminal nonterminal terminal` ?

# Answer
I think that answer is clear (although of course I would do, because I wrote it).

What it says is:

> if you find

$$nonterminal\\; TERMINAL$$

> in any production, then you add the precedence relations $TRAIL \gtrdot TERMINAL$ for every $TRAIL$ in $Trailing(nonterminal)$. Similarly, every occurrence of

$$TERMINAL\\; nonterminal$$

> generates the relationships $TERMINAL \lessdot LEAD$ for every $LEAD$ in $Leading(nonterminal)$.

So in $'(' expr ')'$, you have both an instance of $TERMINAL\\; nonterminal$ and an instance of $nonterminal\\; TERMINAL$, and you need to deal with both of them independently.
> 1 votes

---
Tags: terminology, formal-grammars, parsers
---


# Question
Title: Machine Learning: Identify Patterns in Time-Series Data
I work in renewable energy. My company gathers *a lot* of data from equipment. This typically includes process data (such as transformer temperature, line voltages, currents, etc.) and discrete alarms (e.g. breaker trip, inverter alarm values, transformer over temperature alarm). This is a rough example of what our data looks like (to be read as lines of csv):

* timestamp, tag, value
* 5/25/2016 14:30:01, INVERTER\_1.VOLTAGE\_DC, 249.5
* 5/25/2016 14:30:06, INVERTER\_1.VOLTAGE\_DC, 250.1
* 5/25/2016 14:45:02, TRANSFORMER\_1.TEMP\_ALARM, 0
* 5/25/2016 14:45:15, TRANSFORMER\_1.TEMP\_ALARM, 1

I'd like to start performing some pattern analysis on this data at rest, not real-time (at least for now). I believe what I'd like to attempt is unsupervised feature learning, but I'm not entirely sure. It would be nice (I think) to apply machine learning to 1) identify any patterns that aren't obvious and 2) allow an algorithm to identify signatures of patterns in the data (e.g. all inverters on a single feeder lose communications when a breaker is open).

My initial question: Is this considered time-series data? In my research so far it seems that time-series data is referencing data that is a function of time. For most of my data, as a domain expert, I don't believe that defining functions for my data is useful for this analysis. Also, in my research, it seems as though time-series data refers to real-valued values and not discrete.

Any comments or relevant references would be helpful.

# Answer
Yes, your data is "time-series data", since it's a sequence of measurements of the same variable collected over time. Time-series data can be collected continuously or at discrete intervals.

Your sample data *can* be expressed as a function of time - maybe it helps to think of the "function" as the process that produces the measured output, the input to the function is the date/time stamp, and the output is the value of that parameter at that time:

$\text{INVERTER\_1.VOLTAGE\_DC}( \text{5/25/2016 14:30:01} ) = 249.5$

You don't necessarily need to define the (general) function(s) that produce your data to perform time-series analysis - it's enough to know the value of the function at your measurement times. The range of time-series data can be continuous & real-valued, discrete, or even non-numeric.

It's certainly possible to use machine learning techniques on time-series data, e.g. for forecasting, anomaly detection, or pattern identification.

Neural nets might be a good choice if you're interested in predictive modeling. One possible setup is to use the current parameter measurements as input to the neural net, and the output is the predicted future value or "state of the system" (e.g., whether a breaker is open or not).

WEKA is a good open-source machine-learning toolkit that contains implementations of many different ML algorithms.
> 3 votes

---
Tags: machine-learning, data-mining, pattern-recognition, time-series-analysis
---


# Question
Title: If Data-Flow Analysis is able to approximate, what does that mean?
I have been learning about data-flow analysis and have come across the idea of approximations and that the data-flow analysis should be able to under and over approximate a situation. For example, when using available expressions, we under under-approximate if we aren't sure if we can do something by not doing it. I just don't really understand; surely if analysis wasn't sure if it could do something or not, the algorithm would just not report this as a possible available expression?

What does approximation and decidability (which I think is also related) mean in terms of data-flow analysis?

# Answer
> 2 votes
All of the problems we want to solve with static analysis are undecidable. We have a yes-or-no question ("will this expression be available?", "is this variable live?", etc.). Ideally we'd like an algorithm that takes as input the program, terminates in a finite amount of time, and outputs the correct answer to the question. Unfortunately, the problem is undecidable, so there is no such algorithm.

But we're not willing to give up. So, we accept algorithms that always terminate but sometimes output "I'm not sure". There are basically two kinds of such algorithm. One can will either output "Definitely yes" or "I'm not sure (might be yes, might be no)". The other kind will either output "Definitely no" or "I'm not sure (might be yes, might be no)".

Underapproximation vs overapproximation just refers to the difference between those two kinds of algorithms.

How do you pick one or the other? That depends on what you're ultimately trying to achieve. In some situations, it's more useful to know that the answer is "definitely yes". In others, it's more useful to know that the answer is "definitely no".

Of course, these two notions can be combined, so you can get an algorithm that will output either "Definitely yes", "Definitely no", or "I'm not sure (might be yes, might be no)". But you can't avoid the possibility of an "I'm not sure" answer; that's an unavoidable consequence of undecidability.

---
Tags: terminology, data-flow-analysis
---


# Question
Title: How do you prove that polynomial reductions are not symmetric?
How would I go about showing that L $\leq\_p$ L' does not necessarily imply L' $\leq\_p$ L? I was thinking I should show an example of two problems, where one can reduce to the other but not the other way round, but am not sure what such problems could be.

# Answer
> 4 votes
You have a good plan of approach. Now you need to spend some more time pursuing this. Try to come up with a list of languages $L$ you've seen before, and try different pairs to see if they satisfy the condition. After some trial and error you should be able to solve your problem.

# Answer
> 4 votes
Maybe this insight will be helpful (along with your own thoughts and D.W.'s answer):

Quite intuitively, the relation $A \le\_p B$ indicates that $B$ is more "difficult" than $A$. Indeed, for an NP-hard problem, like SAT, we know that all other NP languages $A$ can be reduced to it, which makes it "the hardest".. But not all languages are NP-hard, some languages are "easier" than others..

---
Tags: complexity-theory, reductions
---


# Question
Title: How do we know for sure that EXPTIME ≠ P?
I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It makes absolute sense *intuitively* that this is the case, as does P≠NP. From what I understand, the time hierarchy theorem states that given more time, a turing machine can solve harder problems.

I have 2 questions:

1. How is the time hierarchy theorem (or anything else) used to prove that P≠EXPTIME?
2. If we assume P=NP and NP=EXP, P=EXP and that contradicts P≠EXP. So one of those statements MUST be false. But we can only conjecture that both these are false, and can't prove it? Is that the case?

# Answer
> 6 votes
1. The time hierarchy theorem says that, for any reasonable function $f$, there are problems that can be decided in time $O(f(n))$ that cannot be decided in time, say, $O(f(n)/n)$. (There are various versions of the time hierarchy theorem. The one I've just quoted isn't standard but it's strong enough to prove what we need, here.) In particular, then, there are problems that can be solved in time $O(2^n)$ that cannot be solved in time $O(2^n/n)$ so, in particular, cannot be solved in time $O(n^k)$ for any $k$. These problems are in **EXP** but not in **P**.
2. Correct: we conjecture that **P$\\,\neq\\,$NP** and **NP$\\,\neq\\,$EXP** but we don't have a proof of either of those things.

---
Tags: complexity-theory, np-complete, np, nondeterminism, polynomial-time
---


# Question
Title: What is the difference between a Neural Network, a Deep Learning System and a Deep Belief Network?
What is the difference between a Neural Network, a Deep Learning System and a Deep Belief Network?

As I recall your basic neural network is a 3 layers kinda thing, and I have had Deep Belief Systems described as being neural networks stacked on top of each other.

I've not til recently heard of a Deep Learning Systems, but i strongly suspect it is a synonym for Deep Belief System. Can anyone confirm this?

# Answer
> 10 votes
artificial neural networks models were generally restricted to only a few layers, say 3, for decades, for various reasons, including a math proof named Kolmogorovs thm that indicated they could theoretically approximate arbitrary functions with low error (but only with many neurons).

multilayer networks beyond that were not feasible/effective via prior learning techniques. a similar breakthrough came in 2006 by 3 different researchers Hinton, Le Cun, Bengio who were able to train much more layers. the prominent problem in this area was handwriting recognition.

the term "deep belief network" seems to originate with a 2006 paper by Hinton referring to Bayesian networks, which have close conceptual/theoretical connections/analogies with neural networks. "A fast learning algorith for deep belief nets"

see slide 17 in particular of this presentation deep neural networks

so the deep learning field is only ~½-decade old and is undergoing rapid research and development. Google, Facebook, Yahoo have all anounced deep-learning based initiatives and R&D is ongoing.

# Answer
> 14 votes
Artificial neural networks is a class of algorithms that include a lot of different kinds of algorithms based on graphs, so I won't detail here beyond what you asked because there's too much to say, since there are so many kinds of ANNs.

The first kind of artificial neural networks, the famous McCulloch-Pitts neurons, were **linear**, meaning that they could only solve linear decision problems (ie, datasets that could be **linearly separable** by drawing a line). Over time, this linear neural network model became known as the Perceptron or Adaline (depending on how you compute weights update).

**Linear neural networks** are just composed of a bipartite graph, where the left side nodes are the inputs and the right side nodes the output. Only the weights of the edges between these nodes are learnt (the nodes activation threshold can also be adjusted but this is rarely done).

A big step was taken when **shallow** neural networks were invented: instead of having only a bipartite graph, we use a 3partite graph: the input "layer", the output "layer", and **one "hidden layer"** between them. Thank's to the hidden layer, the network can now take non-linear decisions, and solve problems such as the canonical XOR.

Note that the "shallow" term was coined retrospectively when **deep** neural network (also called **n-layers** neural networks) were invented. This is to oppose neural networks with only one hidden layer, with deep neural networks **with n hidden layers**. As you can guess, using more hidden layers allow to decide on more complex datasets since there are more layers to modulate the decision (ie, in other words you're increasing the dimensionality of your decision boundary, which can lead to overfitting).

You may ask: why did no-one try to use multi-layered (deep) neural networks before? In fact, they did, as early as 1975 by Fukushima with the Cognitron and Neocognitron (which is in fact a convolutional neural network, but that's another story). However, the issue was that noone knew how to efficiently learn such networks, the big issue being the **regularization**. Hinton's AutoEncoders opened the way, and later the **Rectified Linear Units of LeCun** fixed the issue for good.

What about Deep Beliefs Networks (DBN)? They are just multi-layered semi-restricted Boltzmann machines. So they are a kind of deep neural network, but with a different basic network pattern (ie: the layer, this is the pattern that is repeated): Boltzmann machines are different from other networks in that they are **generative**, meaning that they are usually used to learn from your data to reproduce it ("generate" it), while usual deep neural networks are used to **separate** your data (by drawing a "decision boundary").

In other words, DNN are great to classify/predict a value from your dataset, while DBN are great to "repair" a corrupted data (when I say repair, it's not only from corrupted data, it can also be on a perfectly fine data that you just want to fix a little to be more stereotypical as to more easily recognize with another neural network, such as hand-written digits).

In fact, to neatly summarize, you can say that AutoEncoders are a simpler form of Deep Belief Network. Here is an example of a DBN trained to recognize faces but NOT numbers, the numbers are automatically faded away (this is the "fixing" effect of DBN):

So in the end, DBN and DNN are not opposite: they are complementary. For example, you can imagine a system to recognize hand-written characters that will first feed a character's image to a DBN to make it more stereotypical and then feed the stereotyped image to a DNN that will then output which character the image represents.

A last note: Deep Belief Nets are very close to Deep Boltzmann Machines: Deep Boltzmann Machines use layers of Boltzmann Machines (which are bidirectional neural networks, also called recurrent neural networks), while Deep Belief Nets use semi-restricted Boltzmann Machines (semi-restricted means that they are changed to unidirectional, thus it allows to use backpropagation to learn the network which is way more efficient than learning a reccurent network). Both networks are used for the same purpose (regenerating the dataset), but the computational cost is different (Deep Boltzmann Machines are significantly more costly to learn because of its recurrent nature: it is harder to "stabilize" the weights).

Bonus: about Convolutional Neural Networks (CNN), you will find a lot of contradictory and confusing claims, and usually you'll find that they are just deep neural networks. However, it seems the consensus is to use the original definition of Fukushima's Neocognitron: a CNN is a DNN that is forced to extract different features at different hierarchical levels by imposing a convolution before the activation (which a DNN can naturally do, but forcing it by setting a different convolution/activation function on different layers of the network may yield better result, at least that's the bet of CNN):

And finally, for a more rigorous timeline of Artificial Intelligence, see here.

# Answer
> 3 votes
Deep Neural Networks are Neural Networks which have relatively high depth. They are a subclass of Neural Networks. The idea actually goes back decades and is not new. What is new is that we have figured out how to train them in practice. The reason it has become very popular recently is training them became feasible and people used them to beat state of art algorithms. DNN need a lot of data and a lot of computational power which were not available decades ago. Geoff Hinton and his students and colleagues figured out how to train them in practice over the past decade and used them to beat the state of art machine learning algorithms in several fields where most researchers shunned the idea of using them completely at the time.

Belief Networks are a class of Probabilistic Graphical Models, they model a bunch of random variables and their dependencies using a graph (there are various ways to do this). Those variables themselves can be from parameterized distributions and might be modeled by neural networks (or some other model for representing parameterized distributions). Deep Belief Networks are Belief Networks which have relatively high depth.

Belief Networks tend to be generative, i.e. we can use a trained model to generate samples from the distribution it represents.

Neural networks tend to be discriminitive, we can use them to compute the probability of a given input (is this a picture of a cat? what is the probability of this being a picture of a cat?) but usually not for sampling (generate a picture of a cat).

# Answer
> -1 votes
Neural networks are normally implemented where hidden layers and quadratic equations are required.where as deep learning and deep belief networks are utilized where multiple hidden layers are required for manipulation of data just like deep Boltzmann networks.

---
Tags: machine-learning, neural-networks, boltzmann-machine
---


title: Why is bipartite graph matching hard?

text:
# Question
Title: Why is bipartite graph matching hard?
I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me it seems trivial.

The method of solving the problem says to convert the original bipartite graph into a network, by creating a Source and Sink vertices, directing all edges towards the Sink and setting all edges' capacity to 1. Then I should run Ford-Fulkerson. Fair enough.

My question is, can't I just do this linearly? (Obviously not, but I don't see why). The goal of the problem seems to be to find a maximum matching in a complete bipartite graph - i.e. the maximum number of edges between the two "sections" of the graph that do not share any vertices.

To illustrate, see this picture

* In the first graph the maximum matching will be 2 - any of the two vertices on the right may only be connected to a single vertex on the left. Since the edges are unweighted, it doesn't really matter which?
* Similarly in the second graph, the matching will again be just 2.

Can you tell me where am I thinking wrong? I don't understand where the complexity of the problem comes from.

And sorry if any of the terms were used incorrectly, I am not studying CS in English. Thanks

# Answer
> 5 votes
> I am reading on how \[...\] to solve unweighted bipartite graph matching problem. \[...\] The goal of the problem seems to be to find a maximum matching in a complete bipartite graph

No, the goal of the problem is to find a maximum matching in *any* unweighted bipartite graph.

---
Tags: algorithms, graphs, optimization, bipartite-matching
---


title: RISC machines have register renaming?

text:
# Question
Title: RISC machines have register renaming?
I know that one of the techniques used by RISC machines to improve the pipeline is the delayed branch, but what other techniques do they employ, namely, can they use register renaming?

I know that Superscalar processors have register renaming, but a Superscalar processor can only be a CISC machine, right?

# Answer
> 7 votes
RISC machines *can* have register renaming, just like CISC machines *can* have register renaming. Register renaming is an aspect of the processor implementation, whereas RISC is an aspect of the instruction set, so they are fairly orthogonal: there can be two processors implementing the same architecture (i.e. accepting the same code), but in different ways (and with different performance characteristics), one with register renaming and one without.

The Wikipedia article gives the example of the Alpha 21264. Alpha is pretty strongly on the RISC side.

The Alpha 21264 is considered superscalar, by the way. I don't know why a superscalar processor would have to be CISC or RISC: again, the ability to process multiple instructions in parallel is orthogonal to the complexity of the instruction set. In fact, RISC processors are more likely to be able to parallelize instruction execution successfully, because the instructions are easier to analyze. But CISC processors can and do do it too.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: Exponential example for simplex used in SMT solvers
The original simplex algorithm requires an exponential number of pivot operations in the *worst* case, e.g., if run on the Klee-Minty example \[3,4\].

What about the simplex algorithm used in SMT solvers \[1,2\]? **Could you provide an example where it requires exponential time?**

The algorithm I have in mind is by Bruno Dutertre and Leonardo de Moura in \[1,2\], and is presumably used in all modern SMT solvers. The algorithm introduces one slack variable per constraint, the slack variables have lower and upper bounds; and the problem is that of *feasibility* instead of *optimization*.

I tried to modify the Klee-Minty example \[3,4\], but failed so far. Kroening & Strichman contains this question as an exercise, so you can also hint instead of answering.

---

1. Integrating Simplex with DPLL(T) by Bruno Dutertre and Leonardo de Moura:
2. Decision Procedures: an Algorithmic Point of View by Daniel Kroening and Ofer Strichman
3. Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method
4. Picture of the Klee-Minty cube:

# Answer
Here, you can find hard examples for DPLL. http://www.ioc.ee/~tarmo/tday-torve/itsykson-slides.pdf

For instance, it can be very slow for Tseitin formulas and for some unsatisfaisable formulas (it will try many solutions).

I hope it will give you some hints :)
> -1 votes

---
Tags: linear-programming, smt-solvers
---


# Question
Title: Is better than O(n^2) possible for getting pairs that sum to a multiple of 10?
Is it possible to solve a problem with a worse case less than $O(n^2)$, when the input is an an array of numbers and the output is all pairs that sum to a number divisible by 10? for example

```
int [] a = {1, 2, 15, 25, 28};
// would produce [2, 28], [15, 25]

```

I don't think so because when all sums are divisible by 10 then the total number of pairs is $n(n-1)/2$ which is $O(n^2)$.

```
int [] a = {5, 15, 25, 35, 45};
// n(n-1)/2 = 5(4)/2 = 10
// pairs [5, 15], [5, 25], [5, 35], [5, 45], [15, 25], [15, 35], [15, 45], [25, 35], [25, 45], [35, 45]

```

# Answer
It is not possible to have an algorithm that is faster than $O(n^2)$ as the output can be $O(n^2)$ — all pairs. This can happen when all numbers are divisible by 10, or all are returning 5 when taken modulo 10.
> 3 votes

---
Tags: complexity-theory, time-complexity, arrays
---


# Question
Title: NP-hardness of an optimization problem with real value
I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$.

I have been able to reduce an NP-complete problem to my own problem in polynomial time. I also showed that my problem is NP.

Since the input to the decision problem is a real value, is this reduction valid and can I categorize my problem as NP-complete?

Edit: What if the precision of this real number is limited to $\frac{1}{polynomial(n)}$, which means that the solution is a real number with a polynomial precision.

# Answer
> 2 votes
Yes, you can categorize your problem as in NP and is NP-complete if you have the followings:

* The set of real numbers from which you draw the number from and you use as input into your procedure is countable

In this case, you can represent your input as proper input into Turing machine because you can encode any countable set. Remember that a union of a finite number of countable sets is still a countable set.

To be more concrete, for example, if your real numbers are restricted to something like the set of all rational numbers $Q$ (countable) union with the set of all $\sqrt{x}$ where $x \in Q$, then you still have countable set (you can add $\sqrt\[3\](x)$, $sin(x)$, $log(x)$, etc.. as long as the number of them is finite). Your problem is still in NP and is NP-complete even though the numbers are real numbers.

Nevertheless, as the previous answer points out, if your real numbers form a smooth set, then it is another case which will be very interesting to think further.

# Answer
> 3 votes
No, you can not say that your problem is NP-complete.

The reason is that it is not in NP: there is no Turing machine at all (let alone a poly-time (non-deterministic) one) that can solve it because TMs can not handle real numbers.

The reduction may still go through and show that the problem is NP-hard; a subset of the reals should certainly suffice to model the naturals in Vertex Cover or whatever NP-complete problem you use. So it is, in principle, possible to define a computable, poly-time reduction function that does the job. It will output naturals (or integers, rationals, ...), of course, but as long as you are willing to accept these as real numbers you are fine.

This reduction is likely to carry over to restricted versions of your problem (e.g. finite precision) which *can* be classified in the framework of computabilty/complexity theory.

# Answer
> 0 votes
The book Complexity and Real Computation extended the Turing machine and extensively discussed the computational complexity problem for algorithms involving real numbers. For example, the authors extend the concept of NP to such algorithms.

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


# Question
Title: Find a DFA for a finite set of palindromes
Since every finite language is regular, I'm trying to find how would a DFA for the following language $\\{xx^R \mid x \in \\{a,b\\}^\*, |x| = \ell\\}$ look like. Would there be one DFA for all words of length $\ell$ or one DFA per word?

# Answer
To add to Denis' answer, depending on your tastes, one could also (trivially) construct a collection of FAs $M\_i$ such that $M\_i$ accepts only $w\_i$ and from those construct a NFA by adding a new start state and linking that state to the original start states of each $M\_i$ by $\epsilon$-moves. Having done that, constructing an equivalent DFA $D$ is straightforward, by a well-known process. In other words, we construct one DFA for each word and use them to construct one DFA for all words.
> 2 votes

# Answer
Consider a finite language $L$ over alphabet $\Sigma$, i.e., $|L| = k \< \infty$. Let's enumerate all words of $L$ as follows $w\_1, w\_2, \ldots, w\_k$. Let $S$ be the set of all prefixes of words of $L$. Create a DFA as follows: introduce a state $q(x)$ for each $x \in S$. For each compatible $x$ and $a$, define a transition rule $q(x) \rightarrow^a q(x a)$ where compatible means $x \in S$, $a \in \Sigma$, and $x a \in S$. Make states $q(w\_i)$ accepting for each $i \in \\{1, \ldots, k\\}$. Any undefined transition leads to rejection. This DFA clearly accepts the $w\_i$ and nothing else.

You can apply this construction to your particular case $L = \\{ x x^R \mid x \in \\{a,b\\}^\*, |a| = \ell\\}$ with $|L| = 2^\ell$, i.e., there will be one DFA accepting all relevant words of length $\ell$. For example, consider $\ell = 1$. This means your $L = \\{aa, bb\\}$. The set of prefixes $S = \\{\epsilon, a, b, aa, bb\\}$. Your accepting states are $q(aa)$ and $q(bb)$ and your transition rules are $q(\epsilon) \rightarrow^a q(a)$, $q(a) \rightarrow^a q(aa)$, $q(\epsilon) \rightarrow^b q(b)$, $q(b) \rightarrow^b q(bb)$.
> 0 votes

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


# Question
Title: How does (non)deterministic time relate to verifiability?
So far, from all the research I've done, I've come across 2 different ways that NP time is explained. One is that a nondeterministic turing machine is able to solve the problem in polynomial time. It seems like this is the exact same as being able to verify that a result is correct in polynomial time, but not necessarily solve the problem in polynomial time. Both these ideas make sense, but these ideas seem very different to me. One is talking about solvability of a problem in a nondeterministic context while the other is talking about solvability vs. verifiability. Can you please intuitively explain why they're related, and if this relationship between solvability, verifiability, determinism, nondeterminism applies to harder complexity classes such as EXP vs NEXP?

# Answer
Here's some intuition for the equivalence proof

$(\implies)$: Suppose we have a non-deterministic Turing Machine $M$ that solves a problem $P$ in polynomial time. When we run $M$ on some accepted input $x$, we make a bunch of decisions non-deterministically, essentially choosing an execution path. If we record each of those choices, this gives is a string with is polynomial in the size of $x$ (since we know $M$ runs in non-deterministic polynomial time). Then the trace of running $M$ on $x$, with each decision point, is a certificate for $x$. We can follow the steps again and check that any string represents a valid run on $M$, and see whether it ends in a YES or NO state.

$(\impliedby)$: Suppose we have a verifier which takes a string $c$ and input $x$ and checks if $c$ is a valid certificate that $x$ is accepted by problem $P$, where $|c| \leq |x|^k$ for some fixed $k$. Then we can make an NTM which looks at any $x$ and determines whether it is in $P$ by "guessing" non-deterministically guessing a certifier $c$ of length less than $|x|^k$ and running the verifier on that.

EDIT: to apply this to $EXP$ and $NEXP$, just replace the word polynomial with exponential and change the bound on $c$, and the rest should still work. It doesn't really apply to classes like $PSPACE$, since it's not defined in terms of non-deterministic machines. Not being able to make these kinds of guesses are what makes PSPACE harder (as far as we know) than NP.
> 9 votes

---
Tags: complexity-theory, np
---


# Question
Title: Is there a "flaw" in the backpropagation algorithm?
While trying to find a better backpropagation algorithm, I came across a paradox in my algorithm and then I found out this also happens in the usual backpropagation algorithm.

Our neural network looks like this:

In this simple example, we have no biases. The activiation function is the usual $f(x)=\frac{1}{1+e^{-x}}$

Our training set is just one datapoint: input = 0.9 and target\_output = 0.9. The learning factor is set to 0.1.

The paradox happens when w2 is randomly initialized to a negative value. First, let's take a look at the "normal" situation (where the paradox does not happen). Let's say w1 and w2 are both positive, but the output is less than 0.9. w1 and w2 are both initialized at 0.1. Then to reduce the error, both w1 and w2 are increased, so the the output will get closer to 0.9. This is visible in the next graph (x is the training iteration, each training iteration contains one backpropagation).

Now let's take a look at the situation that w1 is intialized at 0.1 and w2 is initialized with a negative value (-0.5). Initially, an increase in w1 would cause a more negative value for the output layer, which increases the error. However, that's only the case because w2 is negative. Although w1 will decrease in the beginning, it will start increasing as soon as w2 becomes positive. The blue line (w1) is clearly decreasing in the beginning in the below graph from my experiment:

This "wrong" learning in the beginning of the blue line w1, is a consequence of using the derivative of the error function to induce small learning steps. Would it be better to somehow anticipate a positive w2 that will be needed anyway and so increase w1 from the beginning instead? Can we make a better backpropagation algorithm?

# Answer
> 6 votes
There's no paradox. This is not a flaw. Nothing is going wrong here. In both examples, you're making steady progress: the output steadily gets (monotonically) closer and closer to the target.

Looking at individual weights (like w1 or w2), there's no reason to expect them to vary monotonically during the learning process. If we perfect foresight and we know what the final optimal values of the weights are, we'd know whether each weight needs to increase or decrease -- but we don't.

Remember that backpropagation is just gradient descent, used to minimize some loss function. Gradient descent is a *local* method for optimization: it makes a locally greedy step. It has no global knowledge and as a result if you look at any single weight (any single coordinate), it won't necessarily vary monotonically: it might increase and then decrease, for instance.

Can you improve on backpropagation? Yes, you can. A large part of the success of deep learning is that researchers have found improvements to gradient descent for training neural networks (e.g., learning rate, momentum, and more). Nonetheless, they're still optimization methods that work by taking a locally optimal step, and so they can be subject to overshoot and to phenomena such as you noticed. Multidimensional optimization is hard. You're going to see this kind of thing happen in pretty much any iterative method for optimization.

Bottom line: This isn't a flaw, this is only to be expected, given the difficulty of multidimensional optimization. You still get to optimal values in the end, and that's almost-miraculous in its own right -- you should be glad for that and not worry too much about the fact that it takes longer to get there than if we already knew what the optimal solution was before we began.

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


# Question
Title: Maximize cost in graph with variable costs
Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous day. The prisoner knows the calories of each dish for the full week, and wishes to maximize his calorie intake for the week.

I modeled the problem into a bidirected cyclic graph: l\[n\], h\[n\] are the two known arrays of costs and k the number of steps taken through the graph. (The cost to the H node at the kth step is h\[k\]). L represents eating the low nutrient dish, while H the high one. If you want to get to H you must pass from - first and amass no cost. The costs represent the nutrients gained when moving to each node. (They could be rewards on the nodes instead). S is the start node. The goal is to maximize the cost, given the number of maximum steps n.

I'm looking for a general direction. Does it belong to a known family of problems? If yes, how do you solve them efficiently? Dynamic programming, knapsack or some known modification of a graph traversal algorithm? Is considering it a graph problem wrong, or not particulartly helpful? Sorry for the barrage of questions.

# Answer
There's no need to introduce a graph; the problem can be solved by a straightforward dynamic programming algorithm. The running time will be $O(n)$, where $n$ is the number of days.
> 0 votes

---
Tags: graphs, dynamic-programming, weighted-graphs
---


# Question
Title: Is there a relationship between "sound and complete" in logic and "type safety" in PLs?
I've been wondering if there's a connection between "good logics" and "good programming languages". It seems that logics are shown to be "locally sound and complete" whereas programming languages are shown to be "type safe" (preservation and progress).

If there's a relationship could you please explain it and give some references so that I can follow up on it.

# Answer
> 6 votes
The concepts of "local soundness" and "local completeness" (which is Frank Pfenning's terminology, originally introduced in his paper with Rowan Davies, A Judgmental Reconstruction of Modal Logic) are a bit more specific than the standard concepts of "soundness" and "completeness" relative to a model as suggested in the title of your question (and as in Andrej's answer). Under the Curry-Howard correspondence, local soundness and local completeness correspond exactly to $\beta$-reduction and $\eta$-expansion of typed terms, respectively.

These are not quite preservation and progress, but preservation is closely related to (and usually relies on the fact that) $\beta$-reduction is type-preserving. The type safety theorem that results from combining preservation + progress is somewhat related to "global soundness" (in the sense of these lecture notes), which is just another name for the normalization/cut-elimination theorem for (a proof system for) a logic. Type safety is a weaker statement, though, since combining preservation with progress only guarantees that a term $t:A$ will either eventually reduce to a value $t \leadsto^\* v$ such that $v:A$ or else fail to terminate. In contrast, the normalization theorem for a logic says that any proof $\pi$ of $A$ can definitely be reduced to a normal proof of $A$.

PL designers have typically paid less attention to $\eta$-expansion, although this is starting to change in languages with more sophisticated type systems (such as proof assistants). In such languages, $\eta$-expansion (and hence local completeness) is closely related to the definitions of equality and/or subtyping.

There is a bit more discussion of local soundness and completeness and their Curry-Howard interpretation in Pfenning's Logical Frameworks — A Brief Introduction.

# Answer
> 7 votes
Soundness and completeness of logic are **semantic** notions which say that logic and its models fit together nicely. We can find similar theorems in the theory of programming languages but they are not necessarily about mathematical models of programming languages.

A general way to understand soundness is that "bad things do not happen" (logic does not prove invalid things). A general way to understand completeness is that "good things happen" (there are sufficiently many models).

A programming language typically has several kinds of semantics:

* **static semantics** explains how to assign types to programs
* **dynamics (operational) semantics** explains how to run programs, more or less
* **denotational semantics** is more akin to models in logic and it explains how to map programs to mathematical objects.

There are theorems which relate these semantics. For instance:

> **Preservation:** If a program `p` has type `T` and `p` evaluates to `p'` then `p'` has type `T`.

This is like soundness (bad things don't happen, namely a program will not become untyped). Another one is:

> **Progress:** If a program `p` has type `T` then it is either a value (it's finished) or it has another step of execution.

This is like completeness (good things happen, namely a program *will* make the next step).

When we put these two together, we get safety.

Another kind of theorems relates denotational semantics to operational semantics. For instance:

> **Adequacy:** if `p` and `q` are denoted by the same mathematical object then they are observationally equivalent.
>
> **Full abstraction:** if `p` and `q` are observationally equivalent then they are denoted by the same mathematical object.

Adequacy says that the model is not too small and full abstraction that it is not too big. It makes a bit less sense to relate these two to soundness and completeness, but if I had to, I would say that full abstraction is like soundness and adequacy is like completeness.

---
Tags: programming-languages, logic, type-theory
---


# Question
Title: What complexity class would this version of generalized chess fall?
By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white *force* a win?" because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

But if you were to ask the decision problem "Given an nxn board with a given position, *can* white win?" and apply it to generalized chess, would this variation be in NP? Because the verifiability of this proof would only require polynomial time (just play out the winning game). For this decision problem, would it fall in NP, because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?

# Answer
> 7 votes
> because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

It is possible that generalized chess is in $NP$. We do not have a proof that $NP \not = EXPTIME$ or a proof that a certificate for generalized chess would take an exponential amount of steps. It is highly likely, though.

> But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP? Because the verifiability of this proof would only require polynomial time (just play out the winning game).

This is unknown. It is known that if two players work together to reach a given position then this may take an exponential amount of moves but this doesn't apply to the specific case of whether white can win and doesn't allow us to conclude whether the problem is in $NP$ or not (because even if it takes an exponential amount of moves, maybe there is a "smarter" certificate that can prove this exponential sequence of moves exists in polynomial time).

> because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?

No. Shortest path can be solved in exponential time (polynomial time even) and is in $NP$, but it's (likely) not $NP$-complete. Moreover, it is possible that there are problems that require exponential time to be solved and are in $NP$, but that are not $NP$-complete, see e.g. $NP$-intermediate.

# Answer
> 1 votes
> But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP?

Probably. In fact, I suspect it would be in logspace or perhaps even a smaller complexity class. Determining that white can win involves barely more than checking that the position isn't a stalemate, white isn't already checkmated and white has sufficient material to checkmate (from memory, a queen; a rook; two bishops; three knights; a bishop and a knight; or a pawn, via promotion). That doesn't quite work, since it could be that black's only legal moves unavoidably force checkmate or force the loss of sufficient mating material for white. But it feels pretty close to the truth.

> Because the verifiability of this proof would only require polynomial time (just play out the winning game).

That's not true because there's no guarantee that the number of moves required is bounded by some polynomial in the size of the input.

> For this decision problem, would it fall in NP, because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?

No, that's not the definition of **NP**-completeness. While it's a reasonable intuition that a problem being **NP**-complete means that we don't know any algorithms that are better than exponential, **NP** does *not* mean "it takes exponential time on a deterministic TM." Being **NP**-complete means that the problem is in **NP** and every other problem in **NP** reduces to it by, say, a polynomial-time many-one reduction.

---
Tags: complexity-theory, time-complexity, np, nondeterminism, board-games
---


# Question
Title: How to use an old SAT solver to discover a new one, as is done in The Golden Ticket?
In Lance Fortnow's book *The Golden Ticket*, he mentions that once you have a polynomial-time algorithm for an NP-complete problem, you can use it to find a faster algorithm. Can you tell me how that is done? And once that is done, you can use the new algorithm to discover an even faster one *ad infinitum*, till a fixed point. Below is the exact quote from the book:

> "So what do you ask a genie who will grant you only one wish?" said the adviser.
>
> "I have no idea," replied Steve.
>
> "You ask for a genie who will grant all your wishes."
>
> The proverbial light bulb went off in Steve's head. He knew there must be some better algorithm for solving clique problems out there somewhere, but he couldn't figure it out on his own. But he had the genie, the Tsinghua code, which could search an exponential number of possibilities quickly. *So he wrote up a program that used the Tsinghua routines to search for a better algorithm for NP problems.* He got permission to use the computing resources of the National Center for Supercomputing Applications (NCSA), based at the University of Illinois. After weeks of processing time his work paid off a little bit, finding a new algorithm that had a 5 percent improvement over the Tsinghua code--good enough for a research paper but not enough to make a real impact.
>
> His adviser simply said, "Try again using the new code."
>
> So Steve used his new code to find an even faster algorithm for NP problems. A few weeks later he had a 20 percent improvement.
>
> But his adviser was not impressed. "Try it again."
>
> Steve replied, "Why don't I just set up the computer to automatically keep trying with the new code it finds?"
>
> The adviser gave that look, the look that told a student he had achieved enlightenment, or at least had realized the obvious.
>
> Steve went back to his office and started the tricky process of writing code that searches for faster code, and then used this faster code to find even faster code and continue this process until it could find no further improvement.

Now focus on SAT. MiniSAT is a fast SAT solver, though not to the point of being polynomial-time.

> How to use MiniSAT to mechanically discover a new SAT solver?

# Answer
> 7 votes
Actually, probably you can't use a SAT solver to find another SAT solver, unless something surprising happens.

*If* P = NP, then you can. If P = NP, then the polynomial hierarchy collapses (i.e., P = PH), so there is a polynomial-time algorithm for every problem in PH. The problem of asking whether there is a faster SAT solving algorithm is essentially a $\Sigma\_2$ problem, which is part of the polynomial hierarchy; if the polynomial hierarchy collapses, there's a polynomial-time algorithm for every problem in PH and thus for every problem in $\Sigma\_2$. Thus you can in polynomial time search for a better SAT solver, *if* P = NP.

But most researchers expect that P is not equal to NP, so this statement is most likely moot and unlikely to be helpful in practice.

If P is not equal to NP, then this reasoning doesn't work. In fact, many researchers expect that $\Sigma\_2$ is even harder than NP (there are problems in $\Sigma\_2$ that are harder than any problem in NP), so it would be surprising if there was a simple reduction to express the problem "find me a faster SAT solver" as an instance of SAT. In particular, SAT solvers can solve SAT, or any other problem in NP -- but in any case, only problems in NP. If (as we suspect) $\Sigma\_2$ is harder than NP, then SAT solvers can't solve problems in $\Sigma\_2$.

Of course, we don't actually know. It's always possible that the conventional wisdom is wrong, and that tomorrow we discover that P is actually equal to NP. That would be a great surprise, but we can't completely rule it out.

*The Golden Ticket* is trying to give a deeper understanding of why complexity theorists consider the P vs NP problem so important and so fundamental. Part of that involves exploring counterfactual worlds and counterfactual assumptions that we suspect are probably false, to see what their consequences would be.

---

Or, to explain it a different way:

The problem is that finding a better SAT solver is a $\exists \forall $ kind of statement. The statement is of the form $\exists A \forall x . P(A,x)$, where $P(A,x)$ is the statement that $A$ is fast and correctly solves the SAT instance $x$. Those kinds of statements can't be solved with a SAT solver. SAT solvers can solve problems of the form $\exists x. Q(x)$. However, $\exists \forall$ statements are harder than $\exists$ statements. This is basically the difference between $\Sigma\_2$ and NP.

---
Tags: algorithms, np-complete, p-vs-np, sat-solvers
---


# Question
Title: What is the difference in 'logical array blocked' and array list B, and what do they represent?
In Johnson's 1975 Paper 'Finding All the Elementary Circuits of a Directed Graph', his psuedocode refers to two separate data structures, logical array blocked and list array B. What is the difference in them and what do they represent? Moreover, what does 'Vk' mean?

# Answer
In the pseudocode, *T array* means an array where each element has type *T*. *Logical* is the type of a boolean (i.e., it can hold the value true or false). *Integer list* is the type of a list of integers.

Thus, in the pseudocode, *logical array blocked(n)* is the declaration of an array called *blocked* containing *n* elements, where each element is a boolean. *integer list array B(n)* is the declaration of an array called *B* containing *n* elements, where each element is a list of integers.

$V\_K$ isn't clearly defined, but from context, I'd guess it is the set of vertices in $A\_K$.
> 0 votes

---
Tags: graphs, discrete-mathematics, graph-traversal
---


# Question
Title: How can I reduce a product of transpositions?
I'm looking for an algorithm to solve the following task:

Input: a set $T$ of transpositions; a permutation $\pi$ expressed as a product of transpositions from $T$
Desired output: express $\pi$ as the shortest possible product of transpositions from $T$.

In other words, the output should be a list of transpositions $\tau\_1,\dots,\tau\_k$ such that $\pi = \tau\_1 \circ \dots \circ \tau\_k$, $\tau\_1,\dots,\tau\_k \in T$, and $k$ is as small as possible.

Is there an algorithm for this that will be efficient in practice?

For example, if I were given (2,3)(0,3)(0,3)(2,6)(2,3)(2,6)(0,3) = (0623), I could reduce it to (2,6)(2,3)(0,3) = (0623).

I have come up with a few methods, based on the following properties:

1. The product of identical transpositions cancel. For example, (1,2)(1,2)(2,3) = (2,3).
2. Any product of the form (x,y)(y,z)(x,y) is equal to (y,z)(x,y)(y,z).
3. Any transpositions which share no elements commute. That is, (u,v)(x,y)=(x,y)(u,v).

I have three methods, based on these three properties:

1. One simple method is simply finding instances of (1). In the first example, (0,3)(0,3) appears as a product, so I may remove those transpositions.
2. Another method is finding instances of (x,y)(y,z)(x,y)(y,z), since this is equal to (y,z)(x,y)(y,z)(y,z) = (y,z)(x,y).
3. A third method is to recognize if identical transpositions are separated by disjoint transpositions. For example, (0,3)(2,6)(0,3) = (0,3)(0,3)(2,6) = (2,6).

Are there any other methods I am missing here?

I will explain some of the context in which this problem appears. Consider a graph G with labelled vertices. On each vertex lies a pebble, $p\_i$. A transposition in the given product corresponds to selecting an edge in G and swapping the pebbles that are incident to that edge.

Therefore, a product of transpositions corresponds to a process of exchanging pebbles of edges, and the end result is a permutation of the pebbles on G which is described by the permutation given by the product of transpositions.

Hence, this process of boiling down a product of transpositions is an attempt to reduce the number of exchanges needed to achieve any permutation of pebbles on a graph G.

# Answer
I suspect your problem is NP-hard, but if you need to solve it in practice, I recommend using a SAT solver to help you.

## Algorithms

I suggest you solve this using a SAT solver. The problem can be expressed in a fairly straightforward way as an instance of SAT, and then you can apply an off-the-shelf SAT solver.

Let's solve the following problem:

Input: $\ell \in \mathbb{N}$; a set $T$ of $m$ transpositions; a permutation $\pi$
Question: Does there exist a way to express $\pi$ as a product of $\le \ell$ transpositions?

We'll construct a way to solve this problem using SAT, then apply binary search over $\ell$ to find the optimal solution.

For simplicity, add the identity element to $T$. Then we can replace "$\le \ell$" with "exactly $\ell$". Now the question can be expressed in a rather straightforward way as a CNF formula.

In particular, introduce boolean unknowns $x\_{i,\tau}$ (for each $i=1,2,\dots,\ell$ and each $\tau \in T$), with the intended meaning that $x\_{i,\tau}=1$ means that $\tau$ is the $i$th transposition in the output sequence. Also, introduce boolean unknowns $y\_{i,j,k}$, where $y\_{i,j,k}=1$ is intended to mean that the first $i$ transpositions in the output sequence map $j$ to $k$. We add constraints:

* For each $i$, we require that exactly one of the $x\_{i,\tau}$ is 1.
* We require that the product of the transpositions yields $\pi$, i.e., $y\_{\ell,j,\pi(j)}=1$ for all $j$.
* We require that the $x$'s and $y$'s are consistent, e.g.,

$$y\_{i+1,j,k} = \bigvee\_{\tau} y\_{i,j,\tau^{-1}(k)} \land x\_{i,\tau}.$$
* We require that $y\_{0,j,j}=1$ for all $j$ and $y\_{0,j,k}=0$ for $j \ne k$.

Now feed this to a SAT solver. This should be satisfiable if and only if there's a way to express $\pi$ as a product of $\ell$ transpositions from $T$.

Finally, use binary search on $\ell$, as mentioned above, to find the shortest possible way to express $\pi$ as a product of transpositions from $T$.

(There are many different ways to express this problem as SAT, and those choices might affect the performance of the SAT solver. So, if you need to solve this in practice, you might experiment with different ways of encoding the constraints into SAT.)

## Hardness

I suspect your problem is NP-hard.

Researchers have studied a natural generalization of this problem where the set $T$ is allowed to contain arbitrary permutations, rather than just transpositions:

Inputs: $\ell \in \mathbb{N}$; a set $S$ of permutations; a permutation $\pi$
Question: Is there a way to express $\pi$ as a product of $\le \ell$ permutations from $S$?

This problem is NP-hard, as proven in the following paper:

The Minimum-Length Generator Sequence Problem is NP-Hard. S. Even, O. Goldreich. Journal of Algorithms, vol 2, pp.311-313, 1981.

This problem remains NP-hard even if \ell is specified in unary (i.e., there is not likely to be an algorithm that is polynomial in the length of the output). Subsequent work showed that the problem is PSPACE-complete if $\ell$ is specified in binary. That's not the same problem as yours, because you have the extra condition that $T$ contains only transpositions, but it is related.

A subsequent paper showed that if $T$ generates a transitive group, then the problem is NP-hard. In your case, this corresponds to the condition that the underlying graph be connected. I suspect you're dealing with a connected graph (otherwise you can trivially decompose into connected components and the complexity will depend on the size of the largest connected component). As a result, this appears to imply that your problem is NP-hard.

This hardness result is mentioned in Section 4 of the following paper:

The complexity of finding minimum-length generator sequences. Mark R. Jerrum. Theoretical Computer Science, vol 36, pp.265--289, 1985.

Assuming this is right, your options are to either look for a heuristic that will be always-efficient but not-always-optimal, or look for an always-optimal algorithm whose running time is not guaranteed to be always-efficient (e.g., by using a SAT solver).

Caveat: I don't have 100% confidence in my reasoning here. If I understand things correctly, it seems to contradict another claim in the same paper (namely, the one mentioned below about adjacent transpositions; those generate a transitive group, yet the corresponding problem isn't NP-hard). So I don't have full confidence that the problem is NP-hard. It's entirely possible I've misunderstood something or mis-applied the paper's results.

## Other resources

Subsequent work has also shown that certain special cases can be solved in polynomial time, e.g., where $T$ contains all transpositions, or where $T$ contains all adjacent transpositions $(i,i+1)$, or where $T$ contains all cyclicly adjacent transpositions (i.e., all transpositions of the form $(i,i+1)$ together with $(n,1)$). However, that's probably not useful to you, as those correspond to rather trivial graphs (the complete graph, a line graph, or a $n$-cycle $C\_n$).

You might also be interested in https://cstheory.stackexchange.com/q/21899/5038
> 1 votes

---
Tags: algorithms, optimization, permutations
---