title: Is the following NP-complete?

text:
# Question
Title: Is the following NP-complete?
I have encountered the following problem.

We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $\[1..Y\]$ and horizontal axis $\[1..X\]$. We can perform the action of removing all points with vertical coordinate $y$, in short removing $y$.

What is the least number of $y$'$s$ we must remove so that the number of $x$ that have points is less than $X/2$. For example in the graph above removing 1 and 2 leaves points only in 1,3,6,9.

This seems like a NP-complete problem to me so the only solution I have developed is removing all combinations of $y'$s. I would be grateful if someone experienced in computation-theory could point me to a similar known problem (or maybe a problem this could be reduced to), any suggestion is welcome.

# Answer
If you mean by "the number of $x$ that have points" that the number of distinct values $x$ such that there is a point $(x, y)$ such that $y$ has not been removed is at most $X/2$, then your problem is extremely similar to Set Cover, which is $\mathbf{NP}$-complete.

Your problem would be the variant in which you ask for the minimum number of sets needed to cover half the elements of your universe. I would be very surprised if this was not $\mathbf{NP}$-complete. I'll think about it some more and update this if I think up a proof of $\mathbf{NP}$-completeness.
> 3 votes

# Answer
I can think of a **O(n log n)** solution:

* Input: the set of all 2-D points on your graph in the form of `(a, b)` \- where `a` is the x-coordinate and `b` is the y-coordinate. Assumption: points are unique. **O(n)**
* Build a HashTable to count the occurrences of each distinct y-coordinate, `b`, over this set. (i.e. `b` is the key and its occurrence is the value) For example: 5 total points with `b==3`, 4 total points with `b==7`, etc. **O(n)**
* Sort the HashTable in descending order on `b`, based on its occurrence count: largest occurrence count first. **O(n log n)**
* While number of x that have points is still more than X/2, loop: **O(n)**
    + Remove the top entry in the sorted result from the HashTable **O(1)**
    + (number of x remaining) = (number of x remaining) - corresponding occurrence count with this entry. **O(1)**
    + Increment a count of how many entries removed so far **O(1)**
* Output the count of how many entries removed, and that is the minimum number of y's that you have to remove to get number of x's that have points less than X/2

Total complexity:

* Runtime: **O(n log n)**
* Space: **O(n)** (to store input and to build the HashTable)

Here's a walkthrough of the algorithm with the example provided by your image:

We have as input the points:

```
(1, 1)
(1, 4)
(2, 2)
(3, 3)
(3, 4)
(4, 2)
(5, 2)
(6, 3)
(7, 1)
(8, 1)
(9, 3)

```

Putting the y-coordinates `b` into a HashTable with `b` as the key and its occurrence as the value:

```
{
    "1": 3,
    "2": 3,
    "3": 3,
    "4": 2,
}

```

This is a sorted order based on the occurrence count, so we first remove y at 1, this removes the points:

```
(1, 1)
(7, 1)
(8, 1)

```

and then move y at 2:

```
(2, 2)
(4, 2)
(5, 2)

```

and we are done.
> 2 votes

---
Tags: complexity-theory, np-complete, computational-geometry
---


# Question
Title: Dynamic programming algorithms with log in the run-time
Most of the classic examples of dynamic programming algorithms have run-times such as $n$ or $n^2$. Are there any natural examples with a $O(n \log n)$ run-time?

# Answer
> 3 votes
One natural example is finding the longest increasing subsequence of a sequence of $n$ numbers. Candidate subsequences can be linked in the input sequence. This is a fairly common exercise, and works for other type of subsequences, too. It is actually the exercise 15.4-6 in the 3rd edition of the Cormen et al. book too. For an algorithm, see Section 2.2 in these notes.

# Answer
> 1 votes
To expand on my comment:

While sorting is not doing a "table lookup", remember the actual definition of DP:

> Method for solving problems that have optimal substructure.

We see that a divide-and-conquer approach for sorting satisfies this.

---
Tags: algorithms, reference-request, dynamic-programming
---


# Question
Title: Do "inductively" and "recursively" have very similar meanings?
Do "inductively" and "recursively" mean very similar?

For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having been determined, and is initialized with the first component, would you call it works recursively or inductively? I have been using "recursively", but today someone said it "inductively".

# Answer
> 6 votes
**No**, but not for the reasons other people have given. The difference between recursion and induction is not that recursion is "top-down" and induction is "bottom-up." Induction is isomorphic to something called "primitve recursion," but, in general, **recursion is strictly more powerful than induction**.

The distinction between top-down and bottom up is trivial -- any "top-down" primitive recursive program can be mechanically converted into something "bottom-up." In fact, any proof by induction can be turned into a recursive program. In the framework of the calculus of inductive constructions, if you want to prove that every natural number is froopulous, you'd write it as a function that constructs a proof that n is froopulous by making a recursive call to construct a proof that n-1 is froopulous.

The key factor of induction is that things are defined in terms of smaller things, and they "bottom out" after finitely many steps. Natural numbers are inductive because every natural is either 0, or the successor of a smaller natural. Lists are inductive because every list is either empty, or can be broken down ("unfolded") into an element and a smaller list.

Sometimes recursive programs aren't written in terms of smaller things though. For example, take this Collatz funtion:

```
fun collatz(n)
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

```

This function goes neither top-down nor bottom-up, and is thus not inductive over the natural numbers.

There might be an ordering to treat that inductively, but for most things there's simply no way. Functions over infinite streams are a great example. In fact, streams are the prototypical example of a "coinductive" type.

Bob Harper's "Practical Foundations for Programming Languages," available free online, has a nice introduction to inductive, coinductive, and recursive types.

# Answer
> 2 votes
To me it mostly is a question of viewpoint. If I define objects based on smaller one, I do it inductively, so that is bottom-up. If I solve a problem by breaking it down in smaller pieces that are solved in the same manner I call it recursion, that is top-down.

(edit) PS. See a similar question in our Mathematics sister department, *Recursive* vs. *inductive* definition. I quote from the answer of Carl Mummert:

> My best description is that "inductive definition" is more common when we are defining a set of objects "out of nothing", while "recursive definition" is more common when we are defining a function on an already-existing collection of objects.

But more importantly:

> it's not worth losing sleep over

# Answer
> 1 votes
No, they're not the same. And you're right (I'm assuming about the algorithm you're describing): it's recursive.

The reason is the definition of both words, which you can read in a dictionary or Wikipedia.

Induction (assuming 'mathematical induction') is specifically about proving that all cases of an argument are true.

Recursion is specifically about a process maybe being repeated in some way within the same process.

*RE: other people's answers:*

After seeing other people's answers, I can understand why there's confusion: when defining datastructures, functions, and languages some theorists seem to use 'inductive' and 'recursive' in a confusing way (see comments to this question). I don't think Koppel's answer (even with current highest votes) really reflects that confusion. Since we are talking about an algorithm, I wouldn't say there are 'inductive algorithms'; I think that's an unnecessary categorization.

---
Tags: algorithms, terminology, recursion, induction
---


# Question
Title: What are the different types of databases?
Is there is a study or classification available on different types of databases? (Examples include structured, unstructured, semi structured relational, object oriented, folksonomies, etc.)

# Answer
One of the key differences between the different paradigms for data management is the underlying structure used to bind pieces of data together. IMHO, the difference between structured, unstructured, semi-structured is not precise enough : the point is that the underlying structure may be more or less flexible. This formal structure is used to define the semantics of the model and so it drives everything: the query language, the concrete (in memory, on disks) data-structures, the graphical representation etc.

In the standard relational paradigm, the core concept is that of a tuple (in the set theoretic sense). XML variants are clearly tree based, RDF related models are grounded on labelled directed multi-graphs: those three models are examplified in this recent draft paper. Nowadays, one talks about stream data models grounded on infinite relations, key-values stores are grounded on functions/maps. I guess folksonomy may be multi-set oriented etc.

So "the study of different types of databases" may turn out to be "the study of formal data-structure useful for large data management".
> 3 votes

# Answer
Wikipedia has a list of database models: http://en.wikipedia.org/wiki/Database\_model
> 3 votes

---
Tags: terminology, reference-request, databases
---


title: Can Santa be both fair and efficient?

text:
# Question
Title: Can Santa be both fair and efficient?
As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning algorithm at least make sure that every kid gets a gift once in a while while Santa *also* serves as many kids as possible each year?

---

Consider a complete graph with real, positive weights and a constant $k$. We want to solve a variant of the Travelling Sales Person problem:

> Is there a circular route of length at most $k$ that serves more than $m$ nodes?

The optimisation version would be:

> Maximise the number of nodes that can be served with a circular route of length at most $k$.

This is motivated by real-world limitations on routes: Santa has one night to deliver as many gifts as possible, a sales person has eight hours for one day's route, and so on.

The first, but not final question is: how hard is this problem? Let's assume we can start at any node, but that should not make too much of a difference.

Now, in order to model fairness, let's assume there are $N$ nodes and we can visit at most $M$ with every tour. Ideally, we would want that every node is visited $t\cdot\frac{M}{N}$ times across $t$ efficient tours. Since there may be bottleneck nodes that have to be visited more often in order to ensure routes visit many nodes, some will inevitably have to be visited less often. That also excludes the trivial approximation of removing once visited nodes until all have been visited.

So, here is the final question. Let $T$ be the number of tours needed until all nodes have been visited by *efficient* $k$-tours. How can we algorithmically determine the minimal value of $T$ (and all the necessary routes)? How complex is this problem?

I guess this is really a multi-criterial problem: each tour should visit as many nodes as possible while we want to keep tours as disjoint as possible.

# Answer
> 5 votes
I am slightly confused. If $k$ is a constant, then you can try all $O(n^k)$ possible tours. Hence the problem is in ${\sf P}$.

However, if $k$ is part of the input, the decision problem is ${\sf NP}$-complete. This can be shown by reducing $\text{HAM-CIRCUIT}$ to the problem, by the following reduction.

Assume that we want to determine if a $n$-vertex graph $G$ has a Hamiltonian circuit. Then we take the complete graph $K\_n$ with the following distance function $$ w\_{ij}:=\begin{cases} 1 & \text{if $(v\_i,v\_j)$ is an edge in $G$} \\ 2 & \text{otherwise} \end{cases}. $$ Furthermore we pick $k=n$ and $m=n-1$.

Let me tell you why this is a reduction. If $G$ has a Hamiltonian circuit, then there is a tour in $K\_n$ with length $n$. In other words a circular route of length $\le n$ that serves $\> (n-1)$ nodes. On the other hand, if there is a Santa-tour that visits $\>(n-1)$ nodes is has to visit all nodes. Since the Santa-tour can only have length $\le n$ and every edge length is at least 1, all $n$ edges in this tour have length 1. Hence this tour corresponds to a Hamiltonian circuit in $G$.

---
Tags: complexity-theory, graphs, scheduling
---


title: Process state in multi threaded process

text:
# Question
Title: Process state in multi threaded process
What would be the process state in a multi threaded process, in which threads are in different states (running, waiting, blocked etc)

# Answer
In short, **the lifecycle of thread does not interfere with the lifecycle of a process**.

Processes and threads have different execution cycles; threads will execute and die while their process will continue to run until it gets a exit, truncate or die call due to normal execution (or in case of deadlock handling).

* If a process contains only one thread, then if the thread is running, the process is in its running state. Otherwise, it can go into ready, wait, or die.
* If a process contains multiple threads, it will execute until all jobs are completed. If a thread goes inactive it will not end a process; a process may enter ready state or be in running state.
> 1 votes

---
Tags: terminology, operating-systems, process-scheduling, threads
---


title: Big Omega of $n \log n$

text:
# Question
Title: Big Omega of $n \log n$
While studying master method at recurrences topic I'm stacked at a point. It is written in the book as:

> $T(n) = 3T(n/4) + n \log n$,
>
> we have $a = 3, b = 4$,
>
> $f(n) = n \log n$, and
>
> $n^{\log\_b(a)} = n^{\log\_4 3} = O(n^{0.793})$.
>
> Since $f(n) = \Omega(n^{\log\_4( 3)+\varepsilon} )$, where $\varepsilon \approx0.2$ ....

The authors means that the $n\log n = \Omega(n)$. How will we know this? Is $n \log n = \Omega(n)$ true? Or something is wrong?

# Answer
> 6 votes
Yes, $ n\log n = \Omega(n) $ is true.

To see why, note that for this to be true, we have to show that $ n\log n \ge cn$ for all $n \gt n\_0 $ and $ \exists c \gt 1 $. If we take $ c = 1 $ then, we get $n\log n \ge n$ for all $n \ge 2$. This shows that $ n\log n = \Omega(n) $ is true.

---
Tags: asymptotics, landau-notation, master-theorem
---


# Question
Title: Does $(a \mid b)^*$ match $a^n$ and $b^n$?
I am getting confused by the regular expression $(a\mid b)^\*$ as it for sure matches $aab$ and $ab$.

Does $(a\mid b)^\*$ also match strings like $aa$, $aaaa$, $bb$ or $bbb$, that is those that use only $a$ or $b$?

# Answer
**Yes**: $(a\mid b)^\*$ is the concatenation of any number of $a$'s and $b$'s, so the expression matches $a^n$ and $b^n$.

As you can read more about on Wikipedia, the vertical bar $\mid$ is the boolean "or" relation (one or the other must be included in the regular expression), while the asterisk $^\*$ indicates that the preceding element is repeated *zero or more* times. Hence:

$(a\mid b)^\*$ is equivalent to $(a\\;|\\;b)(a\\;|\\;b)(a\\;|\\;b)\cdots$ repeated any number of times (even zero).

For each term, you can select either $a$ or $b$, so strings like $aa$, $aaaa$, $bb$ and $bbb$ are valid. In particular, this expression matches the empty string $\epsilon$, which has zero $a$'s and zero $b$'s.
> 6 votes

---
Tags: formal-languages, terminology, regular-expressions
---


# Question
Title: Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$
I went through a question asking me to choose the inherently ambiguous language among a set of options.

$$L\_1 = \\{a^nb^mc^md^n \\;|\\; m,n \geq 1\\}\cup \\{a^nb^nc^md^m \\;|\\; m,n \geq 1\\}$$ $$and$$ $$L\_2 = \\{a^nb^mc^m \\;|\\; m,n \geq 1\\}\cup \\{a^nb^nc^m \\;|\\; m,n \geq 1\\}$$

The solution said that $L\_1$ is ambiguous while $L\_2$ isn't. It generated the following grammar for $L\_1$

$S \rightarrow S\_1\\;|\\;S\_2$

$S\_1 \rightarrow AB$

$A \rightarrow aAb\\;|\\;ab$

$B \rightarrow cBd\\;|\\;cd$

$S\_2 \rightarrow aS\_2d\\;|\\;aCd$

$C \rightarrow bCc\\;|\\;bc$

Now for the string `abcd`, it will generate two parse trees; so it is ambiguous.

But a similar grammar can be created for $L\_2$ too

$S \rightarrow S\_1|S\_2$

$S\_1 \rightarrow Ac$

$A \rightarrow aAb\\;|\\;\epsilon$

$S\_2 \rightarrow aB$

$B \rightarrow bBc\\;|\\;\epsilon$

And it will also generate two parse trees for `abc`. Why isn't it ambiguous then?

If you need, $L\_2$ can be written as $\\{a^nb^pc^m\\;|\\; n=p \\;\\; or \\;\\; m=p\\}$

# Answer
> 13 votes
The question is wrong. The second language is also inherently ambiguous. The usual way this is proved is as follows. Suppose $L\_2$ had an unambiguous grammar. Let $p$ be the constant promised by Ogden's lemma, and consider the word $a^{p!+p} b^p c^p$. Mark the positions of $b^p c^p$ and apply Ogden's lemma to pump this word to the word $a^{p!+p} b^{p!+p} c^{p!+p}$ (Ogden's lemma allows us to pump some $b^q c^q$ for $q\leq p$, and $q|p!$ since $q \leq p$.) Similarly, we can get the same word by pumping $a^p b^p c^{p!+p}$. The two parse trees are different since in the first one most of the $b$s are "closely related" (in terms of least common ancestor) to $c$s, and in the second one it is the other way around.

# Answer
> 6 votes
You're quite right to be dubious, $L\_{2}$ is also inherently ambiguous. It's even been used as a "prototype of an inherently ambiguous language" by Flajolet (right at the start of section 2).

---
Tags: formal-languages, formal-grammars, context-free, ambiguity
---


title: Loop invariants?

text:
# Question
Title: Loop invariants?
```
Insertion-Sort (A) [where A is an array of numbers to be sorted]

(1) for j = 2 to A.length
(2)       key = A[j]
(3)       i = j -1
(4)       while i > 0 and A[i] > key
(5)              A[i+1] = A[i]
(6)              i = i - 1
(7)       A[i + 1] = key

```

CLRS proves the correction of the above algorithm by using a loop invariant:

> **Loop Invariant:** At the start of each iteration of the for loop of lines 1–8, the subarray A\[1... j - 1\] consists of the elements originally in A\[1... j - 1\] but in sorted order.
>
> We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant:
>
> Initialization: It is true prior to the first iteration of the loop.
>
> Maintenance: If it is true before an iteration of the loop, it remains true before the
>
> Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

In the explanation of the maintenance aspect of the loop invariant, the following is mentioned:

> Maintenance: A more formal treatment of the this property would require us to state and show a loop invariant for the while loop of lines 5–7. At this point, however, we prefer not to get bogged down in such formalism, and so we rely on our informal analysis to show that the second property holds for the outer loop.

Why would a "formal treatment" require a loop invariant for the while loop? Having one invariant for the outer for loop is sufficient to prove the correctness of the algorithm- why would a "formal treatment" require a loop invariant?

# Answer
The invariant for the outer loop is sufficient, but first you need to prove that it's actually an invariant. For that, you need to provide and prove a precondition and postcondition for every statement inside the loop. And to prove a precondition and postcondition for the inner loop, you need another invariant.

To a human, it's fairly obvious that the inner loop correctly finds the place to insert the next element, and thus we can just use that in an informal argument. But, in formal semantics, we like boil proof to mechanical symbolic manipulations so that they can be checked by machine, and thus we can't do that. Whenever we encounter a statement, we must do as its rules dictate, and for loops, that means provide a loop invariant. See http://en.wikipedia.org/wiki/Hoare\_logic for more details.
> 5 votes

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


# Question
Title: Reducing minimum vertex cover in a bipartite graph to maximum flow
Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim holds).

Intuitively: for each flow, pick one endpoint, then it is a minimum vertex cover in bipartite graph. But can it be shown rigorously?

# Answer
> 3 votes
According to König's theorem, the size of minimum vertex cover in bipartite graph $G$ equals to the size of maximum matching in $G$, and there is an obvious reduction from maximum matching in bipartite graph to maxflow problem.

# Answer
> 2 votes
Call the two partitions of the nodes $A$ and $B$. Add two new nodes, a source $s$ and a sink $t$. Connect the start node to all nodes in $A$ with an edge with max capacity of one. Connect all the nodes in $B$ to the sink with edges with a max capacity of one. And lastly give all the original edges in the graph a max capacity of one. Now finding the max flow from $s$ to $t$ will find the minimum vertex cover.

For each edge $(u,v)$ included in the max-flow, either node $u$ or $v$ will be a part of the minimum vertex cover.

Draw this and you will understand.

---
Tags: complexity-theory, graphs, reductions, network-flow
---


# Question
Title: Call by value-result vs. call by reference?
From my Googling, it appears that call by value-result is similar to call by reference in that it changes values in the caller, but it's different in that the changes don't take place until the callee exits, and that if the same variable is passed as more than one argument, it'll be treated as separate values in the callee instead of the same value as in call by reference.

Neither fact helps me explain why call by value-result produces different output than call by reference in the following code:

```
program Param (input, output);
var
  a, b: integer;
  procedure p (x, y : integer);
  begin
    x := x + 2 ;
    a := x * y ; (1)
    x := x + 1   (2)
  end;
begin
  a := 1 ;
  b := 2 ;
  p (a, b) ;
  writeln (a)
end.

```

Edit: here's my understanding of things: The insight here is that in CBR, in line (1), both `a` and `x` point to the same thing, so assigning to `a` updates both `a` and `x` to `x * y` which is 6. But in CBVR, `a` and `x` point to different things, so line 1 only updates `a` to 6. `x` remains 3. Then CBR updates `a` right away so `a` ends up being 7 outside `p`. But CBVR updates `a` to whatever `x` is at the end of `p`, which is 4, so even though `a` was 6 in line (1), after `p` exits it's changed to 4.

# Answer
> 5 votes
**EDIT:**
An addendum: if you want to "simulate" call by value-result in Pascal (or in another language that supports only call by reference); you can use this trick:

```
procedure p(var x, y : Integer); // simulates call by value-result
var
  xtmp, ytmp : Integer;

  procedure p_hidden(var x, y : Integer); // nested "hidden" procedure
  begin
  ... YOUR ORIGINAL CODE HERE ...
  end;

begin
  xtmp := x; ytmp := y; // use auxiliary variables
  p_hidden(xtmp,ytmp);  // call by ref the nested procedure
  x := xtmp; y := ytmp; // copy values before return
end;

```

A simple method to "visualize" what is happening, is "inserting" the procedure in the point where it is called:

CALL BY REFERENCE:

```
a := 1; b := 2;
p(a, b)
//// procedure p (var x, y : integer);
//// x is the same as a, y is the same as b
//// begin
  a := a + 2 ;  // a = 3
  a := a * b ;  // a = 3 * 2 = 6
  a := a + 1    // a = a + 1 = 7
//// end;
writeln (a)     // prints 7

```

CALL BY VALUE-RESULT:

```
a := 1; b := 2;
p(a, b)
//// procedure p (valres x, y : integer); // by value result
//// x is the same as a, y is the same as b like in a by reference call
  xt := a; yt := b;  // xt and yt are two "new" variables
  //// begin
  xt := xt + 2 ;  // xt = 3
  a := xt * yt ;  // a = 3 * 2 = 6
  xt := xt + 1    // xt = 3 + 1 = 4
//// end;
//// the values of xt and yt are copied back to a and b (x and y) before return
  a := xt;       // a = 4
  b := yt;       // b = 2
writeln (a)      // prints 4

```

# Answer
> 1 votes
I'm not very familiar with Pascal, but there are some scoping issues.

The 2nd line of `p` modifies global variable `a`. When you pass by reference, line 1 of `p` also modifies `x` which is the same as global `a`. When you pass by value, line 1 does not modify global `a`, but line 2 still does, using the local value of `x`, which is global `a + 2`.

If you can, using a debugger to actually step through code like this can be very instructive.

# Answer
> 1 votes
Using the *variables are boxes* analogy.

```
//a := 1

|   1   | <-- Variable a, with holding the value 1
|_______|

procedure f(x: Integer)...

```

**Call by value**: On a call `f(a)`, the value of `a` is loaded (*copied* into the function `f`'s *very own* box `x`. It receives a **copy** of the value.

```
    //f(a)

 a -> |   1   | -- copying -->  |   1   | <- x
      |_______|                 |_______|

```

Here, there are *two* boxes.

---

**Call by reference**: In this case, `f` doesn't get its own box. Instead, you tell `f` what box to work with: In this case, the box called `a`.

```
    //f(a)

 a -> |   1   | <- x -- for the duration of the call f(a)
      |_______|

```

As you can see, there is only one box, but it now has two names.

I lied to you, initially. A variable isn't a box, it's just a name for one.

---
Tags: terminology, programming-languages, semantics, evaluation-strategies
---


# Question
Title: Integer LP formulation and the existence of a solution
A film producer is seeking actors and investors for his new movie. There are $n$ available actors; actor $i$ charges $s\_i$ dollars. For funding, there are $m$ available investors. Investor $j$ will provide $p\_j$ dollars, but only on the condition that certain actors $L\_j \subseteq \\{1,2,...,n\\}$, are included in the cast (all actors $i \in L\_j$ must be chosen in order to receive funding from investor $j$). The producer's profit is the sum of the payments from investors minus the payments to actors. The goal is to maximize this profit.

1. Express this problem as an integer linear program in which the variables take on values on \[0,1\]
2. Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching).

I am lost on both parts for this problem.

# Answer
> Express this problem as an integer linear program in which the variables take on values on \[0,1\]

$$\begin{align} \text{max: } &\sum\_i^m y\_i \cdot p\_i - \sum\_j^n x\_j \cdot s\_j &\\ \text{subject to: } &x\_i \geq y\_j &\forall i \in L\_j \\ &0 \leq x\_i \leq 1 &\forall i \\ &0 \leq y\_j \leq 1 &\forall j \end{align}$$

We see that if we select an investor $y\_j$ we must select all of the investor's actors $x\_i$ for $i \in L\_j$. Our profit is the residual income left over from paying actors.

> Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching)

If our constraint matrix $A$ is totally unimodular, then the relaxed LP is sufficient to give a 0-1 solution.

Sketch: Observe that $A$ is an $N \times M$ matrix where $N = n + m$ and $M = \sum\_j^m |L\_j|$. This defines an incidence matrix of a bipartite graph where each row corresponds to an edge $(y\_j, x\_i)$ with coefficients $(-1, 1)$. We see that any cycle in the graph defined by $A$ will be *balanced*. That is, for any cycle $C$, $\prod\_{e \in C: e=(u,v)} A\_{e, v} = 1$. The proof for this can be done using the fact that any cycle in a bipartite graph is even. The corollary to this is that the incidence matrix for any balanced signed graph is totally unimodular.
> 4 votes

---
Tags: optimization, linear-programming
---


title: Does Max-SNP hard imply NP-hard

text:
# Question
Title: Does Max-SNP hard imply NP-hard
I have difficulties understanding the definition of the class Max-SNP (optimization variant of **strict NP**), thus I have to following basic question:

```
If a problem is known to be Max-SNP hard, does this imply NP-hardness of the problem?

```

# Answer
> 8 votes
$\newcommand{\maxsnp}{\mathsf{Max}\text{-}\mathsf{SNP}}$The definition of $\maxsnp$ gives us the ability to define:

1. Universal ($\forall$) and existential ($\exists$) quantifiers over variables
2. Existential quantifiers over relations

With this definition we can define $\mathsf{Max}$-$\mathsf{SAT}$:

$$\exists x, \forall y \text{ such that } |\psi(y)| \leq |\psi(x)|$$ where $|\psi(x)|$ is the number of clauses satisfied in formula $\psi$ under assignment $x$.

Given that $\mathsf{Max}$-$\mathsf{SAT}$ is $\mathsf{NP}$-$\mathsf{Hard}$, we see that $\mathsf{NP}$-$\mathsf{Hardness}$ is implied from $\maxsnp$.

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


title: Language acceptance by DFA

text:
# Question
Title: Language acceptance by DFA
I have some questions regarding acceptance of a language by DFA

1. Whether more that one dfa accept a language
2. Whether a dfa can accept more than one language

# Answer
> 1 votes
To expand Luke's answer for your second question:

If you fix a DFA (call it $D$), then there are strings that it accepts, let's call the set of those strings $ACC\_D$, and strings which it rejects (which we can call $REJ\_D$). Each input string is either accepted or rejected, then it is either in $ACC\_D$ or otherwise, it is in $REJ\_D$. $$ACC\_D \cup REJ\_D = \Sigma^\*, \quad \text{and} \quad ACC\_D \cap REJ\_D = \emptyset.$$

The set $ACC\_D$ is in fact the "language" that the DFA accepts. So it is clear that there can be only one such language that $D$ accepts. It is the "Largest" such set, since all the strings which are not there must be in $REJ\_D$, ie., they are rejected by the DFA.

# Answer
> 2 votes
1. Yes, there can be many DFAs for a language. Many will be silly though, one way to get another is to add unreachable states to any DFA for the language). It is also possible to have more than one sensible DFA:

These two DFAs both accept $\\{a,b\\}^{\ast}$.
2. On the other hand each DFA accepts *exactly* one language (i.e. no DFA accepts zero languages, or two or more languages) .

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


# Question
Title: How asymptotically bad is naive shuffling?
It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly:

```
for (i=0..n-1)
  swap(A[i], A[random(n)]);

```

Specifically, since at each of $n$ iterations, one of $n$ choices is made (with uniform probability), there are $n^n$ possible 'paths' through the computation; because the number of possible permutations $n!$ doesn't divide evenly into the number of paths $n^n$, it's impossible for this algorithm to produce each of the $n!$ permutations with equal probability. (Instead, one should use the so-called *Fischer-Yates* shuffle, which essentially changes out the call to choose a random number from \[0..n) with a call to choose a random number from \[i..n); that's moot to my question, though.)

What I'm wondering is, how 'bad' can the naive shuffle be? More specifically, letting $P(n)$ be the set of all permutations and $C(\rho)$ be the number of paths through the naive algorithm that produce the resulting permutation $\rho\in P(n)$, what is the asymptotic behavior of the functions

$\qquad \displaystyle M(n) = \frac{n!}{n^n}\max\_{\rho\in P(n)} C(\rho)$

and

$\qquad \displaystyle m(n) = \frac{n!}{n^n}\min\_{\rho\in P(n)} C(\rho)$?

The leading factor is to 'normalize' these values: if the naive shuffle is 'asymptotically good' then

$\qquad \displaystyle \lim\_{n\to\infty}M(n) = \lim\_{n\to\infty}m(n) = 1$.

I suspect (based on some computer simulations I've seen) that the actual values are bounded away from 1, but is it even known if $\lim M(n)$ is finite, or if $\lim m(n)$ is bounded away from 0? What's known about the behavior of these quantities?

# Answer
We will show by induction that the permutation $\rho\_n = (2,3,4,\ldots, n,1)$ is an example with $C(\rho\_n) = 2^{n-1}$. If this is the worst case, as it is for the first few $n$ (see the notes for OEIS sequence A192053), then $m(n) \approx (2/e)^{n}$. So the normalized min, like the normalized max, is 'exponentially bad'.

The base case is easy. For the induction step, we need a lemma:

**Lemma:** In any path from $(2,3,4, \ldots, n, 1)$ to $(1,2,3, \ldots, n)$, either the first move swaps positions $1$ and $n$, or the last move swaps positions $1$ and $n$.

**Proof Sketch:** Suppose not. Consider the first move that involves the $n$'th position. Assume that it is the $i$'th move, $i\neq 1$ and $i \neq n$. This move must place the item $1$ in the $i$'th place. Now consider the next move that touches the item $1$. Assume this move is the $j$'th move. This move must swap $i$ and $j$, moving the item $1$ into the $j$'th place, with $i \< j$. A similar argument says that the item $1$ can only subsequently be moved to the right. But the item $1$ needs to end up in the first place, a contradiction. $\square$

Now, if the first move swaps the positions $1$ and $n$, the remaining moves must take the permutation $(1, 3,4,5, \ldots, n,2)$ to $(1,2,3,4, \ldots, n)$. If the remaining moves don't touch the first position, then this is the permutation $\rho\_{n-1}$ in positions $2 \ldots n$, and we know by induction that there are $C(\rho\_{n-1})=2^{n-2}$ paths that do this. An argument similar to the proof of the Lemma says that there is no path that touches the first position, as the item $1$ must then end up in the incorrect position.

If the last move swaps the positions $1$ and $n$, the first $n-1$ moves must take the permutation $(2,3,4,\ldots, n,1)$ to the permutation $(n,2, 3,4, \ldots, n-1, 1)$. Again, if these moves don't touch the last position, then this is the permutation $\rho\_{n-1}$, and by induction there are $C(\rho\_{n-1})=2^{n-2}$ paths that do it. And again, if one of the first $n-1$ moves here touches the last position, the item $1$ can never end up in the correct place.

Thus, $C(\rho\_n) = 2C(\rho\_{n-1}) = 2^{n-1}$.
> 13 votes

# Answer
After some digging around thanks to mhum's pointer to OEIS, I've finally found an excellent analysis and a nice (relatively) elementary argument (due, as far as I can tell, to Goldstein and Moews \[1\]) that $M(n)$ grows superexponentially fast in $n$:

Any involution $\iota$ of $\\{1\ldots n\\}$ corresponds to a run of the 'naive' shuffling algorithm that produces the identity permutation as its result, since the algorithm will swap $k$ with $\iota(k)$ and subsequently swap $\iota(k)$ with $k$, leaving both unchanged. This means that the number of runs of the algorithm that yield the identity permutation is at least the number of involutions $Q(n)$ (in fact, a little thinking shows that the correspondence is 1-1 and so it's exactly $Q(n)$), and so the maximum in $M(n)$ is bounded from below by $Q(n)$.

$Q(n)$ apparently goes by a number of names, including the *telephone numbers* : see http://oeis.org/A000085 and http://en.wikipedia.org/wiki/Telephone\_number\_%28mathematics%29 . The asymptotics are well-known, and it turns out that $Q(n) \approx C\left(\frac{n}{e}\right)^{n/2}e^\sqrt{n}$; from the recurrence relation $Q(n) = Q(n-1)+(n-1)Q(n-2)$ it can be inductively shown that the ratio $R(n) = \frac{Q(n)}{Q(n-1)}$ satisfies $\sqrt{n}\lt R(n)\lt\sqrt{n+1}$ and from there basic analysis gets the leading $n^{n/2}$ term in the asymptotics, though the other terms require a more careful effort. Since the 'scale factor' $\frac{n!}{n^n}$ in the definition of $M(n)$ is only about $C\sqrt{n}e^{-n}$, the leading term of $Q(n)$ dominates and yields (asymptotically) $M(n)\geq Cn^{(n+1)/2}e^{-3n/2+\sqrt{n}}$.

Goldstein and Moews in fact go on to show in \[1\] that the identity permutation is the most likely for large $n$, so the $\geq$ is in fact a $\approx$ and the behavior of $M(n)$ is fully settled. This still leaves the question of the behavior of $m(n)$ open; I wouldn't be too surprised if that also yielded to the analysis in their paper, but I haven't had opportunity to read it closely enough yet to really get a grip on their methods, only enough to grok the basic result.

\[1\] Goldstein, D. and Moews, D.: "The identity is the most likely exchange shuffle for large n", http://arxiv.org/abs/math/0010066
> 10 votes

---
Tags: algorithms, algorithm-analysis, asymptotics, probability-theory, randomness
---


title: Invariant Proof of For Loops?

text:
# Question
Title: Invariant Proof of For Loops?
From CLRS (third edition, page 19), there is a footnote:

> When the loop is a for loop, the moment at which we check the loop invariant just prior to the first iteration is immediately after the initial assignment to the loop-counter variable and just before the first test in the loop header.

Why is the checking moment specifically chosen to be after the initial assignment but before the first test? Note the excerpt is talking about proving correctness of algorithms using loop invariants.

# Answer
The loop invariant probably involves the loop control variable. If so, it only makes sense to ask if the invariant is true, when the loop control variable is initialized. When the loop control variable is uninitialized, expressions that involve it are undefined.

Consider a simple example, a loop whose purpose is to determine whether all the elements of a (0-based) array $a$ are equal:

```
   all_equal = true
   for (i = 1; i < a.size; i++)
      if a[i-1] ≠ a[i]
         all_equal = false

```

Here the loop invariant is that $all\\\_equal$ is true if and only if the $a\[k\]$ are all equal for each $k$ with $0 \le k \le i$.

This is makes no sense at all unless the loop control variable $i$ has a well-defined value. Before the initialization, it doesn't. After the initialization, we have $i=1$, and the loop invariant is true.
> 7 votes

---
Tags: proof-techniques, correctness-proof, loop-invariants
---


# Question
Title: Reducing the integer factorization problem to an NP-Complete problem
I'm struggling to understand the relationship between NP-Intermediate and NP-Complete. I know that if P != NP based on Ladner's Theorem there exists a class of languages in NP but not in P or in NP-Complete. Every problem in NP can be reduced to an NP-Complete problem, however I haven't seen any examples for reducing a suspected NPI problem (such as integer factorization) into an NP-Complete problem. Does anyone know of any example of this or another NPI-\>NPC reduction?

# Answer
For example, there is a neat classic reduction of factoring to SAT which is also a source of presumed "hard" SAT instances. Basically one uses EE ideas for binary multiplication encoded into the SAT circuit. Think of binary multiplication as an addition of a series of left shifted multiplicands, each "masked" (ANDed) by the bits of a multiplier. The additions can be performed by a binary addition circuit which is a series of full adders.

A talented undergraduate could build this algorithm. I don't know where it was first proposed or implemented in the literature. I would be interested to hear any references.

See e.g. Satisfy This: An Attempt at Solving Prime Factorization using Satisfiability Solvers by Stefan Schoenmackers and Anna Cavender which lays it out in detail. Also the DIMACS SAT challenge starting in the late 90s had factoring instances that were generated by some researchers but possibly the algorithm was not written up seperately in a paper during that era.
> 11 votes

# Answer
Just to be absolutely clear, Integer Factorization is not known to be NP-intermediate, just suspected to be based on the lack of either NP-completeness proof or polynomial-time algorithm (despite lots of work put into both). I don't know of any natural problem (i.e. not constructed by Ladner for the proof) that is definitely NP-intermediate if P and NP are different.

Okay, after that disclaimer, Graph Isomorphism is another likely candidate for a natural NP-intermediate problem. There's a simple polynomial-time reduction from it to Subgraph Isomorphism \- just leave the graphs the same! Graph Isomorphism is just the special case of Subgraph Isomorphism where both graphs have the same size. The final touch is that Subgraph Isomorphism *is* NP-complete.

Apart from that, there is always of course the not-so-informative reduction promised by the Cook-Levin Theorem, we known that any NP-intermediate problem has some nondeterministic polynomial-time Turing Machine that decides it, and we can convert this into an instance of SAT (just have to build the TM!).
> 11 votes

---
Tags: np-complete, reductions, factoring
---


title: Functions between sets?

text:
# Question
Title: Functions between sets?
I recently took a practice exam for the Computer Science GRE and this was one of the questions:

> Assume that set $A$ has 5 elements and set $B$ has 4 elements, how many functions exist from set $A$ to set $B$?

I had no idea what this means, I don't recall ever studying functions between sets, could someone shed some light on this question for me ?

# Answer
> 2 votes
$\newcommand{\stirling}\[2\]{\genfrac{\\{}{\\}}{0pt}{}{#1}{#2}}$Your comment is correct in that there are $4^5=1024$ functions from $A$ to $B$.

Letting $|A| =n, |B| = m$ this can be seen by the identity:

$$\sum\_{k=0}^n \stirling{n}{k} m(m - 1) \dotsb (m - k + 1) = m^n$$

This describes all the ordered partitions of $A$ over $B$ where each partition is an assignment to the same item in $B$.

A less heady explanation (and perhaps easier to visualize) is the following:

We have a vector of length $n$. Each position in this vector can choose $m$ possible values. That is, the $i$th value in the vector represents what $f(a\_i)$ maps to. How many $n$-length vectors over $m$ values can we have? Exactly $m^n$.

---
Tags: combinatorics, sets
---


# Question
Title: Algorithm to pack any small boxes into a big box
I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains as many as possible?

* No rotation is allowed.
* The heavier boxes must not be on the top of the lighter ones.
* Approximation is allowed.

I am looking for the algorithm so I can implement it in a software.

# Answer
> 3 votes
Your problem is called **3D Bin Packing** and is indeed an NP problem.

Looking those key words on Google will yield many articles about more or less complex approximation algorithms that can help you solve this problem.

# Answer
> 0 votes
Your problem is called (multiple constraints) knapsack problem and is indeed an NP problem.

Looking those key words on Google will yield many articles about more or less complex approximation algorithms that can help you solve this problem :)

---
Tags: algorithms, combinatorics, efficiency, approximation, knapsack-problems
---


# Question
Title: Concise example of exponential cost of ML type inference
It was brought to my attention that the cost of type inference in a functional language like OCaml can be very high. The claim is that there is a sequence of expressions such that for each expression the length of the corresponding type is exponential on the length of the expression.

I devised the sequence below. My question is: do you know of a sequence with more concise expressions that achieves the same types?

```
# fun a -> a;;
- : 'a -> 'a = <fun>
# fun b a -> b a;;
- : ('a -> 'b) -> 'a -> 'b = <fun>
# fun c b a -> c b (b a);;
- : (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>
# fun d c b a -> d c b (c b (b a));;
- : ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'd
= <fun>
# fun e d c b a -> e d c b (d c b (c b (b a)));;
- : (((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
   ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'e
= <fun>
# fun f e d c b a -> f e d c b (e d c b (d c b (c b (b a))));;
- : ((((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
     (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
    ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'e -> 'f) ->
   (((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
   ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'f
= <fun>

```

# Answer
> 16 votes
In this answer, I'll stick to a core ML fragment of the language, with just lambda-calculus and polymorphic `let` following Hindley-Milner. The full OCaml language has additional features such as row polymorphism (which if I recall correctly doesn't change the theoretical complexity, but with which real programs tend to have larger types) and a module system (which if you poke hard enough can be non-terminating in pathological cases involving abstract signatures).

The worst-case time complexity for deciding whether a core ML program has a type is a simple exponential in the size of the program. The classical references for this result are \[KTU90\] and \[M90\]. A more elementary but less complete treatment is given in \[S95\].

The maximum size of the type of the type of a core ML program is in fact doubly exponential in the size of the program. If the type checker must print the type of the program, the time may therefore be doubly exponential; it can be brought back to a simple exponential by defining abbreviations for repeated parts of the tree. This can correspond to sharing parts of the type tree in an implementation.

Your example shows exponential growth of the type. Note, however, that it is possible to give a linear-size representation of the type by using abbreviations for repeated parts of the type. This can correspond to sharing parts of the type tree in an implementation. For example:

```
# fun d c b a -> d c b (c b (b a));;
t2 -> t2
where t2 = (t1 -> 'b -> 'c) -> t1 -> 'a -> 'd
where t1 = 'a -> 'b

```

Here is a conceptually simpler example: the size of the type of the pair `(x,x)` is twice the size of the size of the type of `x`, so if you compose the `pair` function $N$ times, you get a type of size $\Theta(2^N)$.

```
# let pair x f = f x x;;
# let pairN x = pair (pair (pair … (pair x)…));;
'a -> tN
where tN = (tN-1 -> tN-1 -> 'bN) -> 'bN
…
where t2 = (t1 -> t1 -> 'b2) -> 'b2
where t1 = ('a -> 'a -> 'b1) -> 'b1

```

By introducing nested polymorphic `let` definitions, the size of the type increases again exponentially; this time, no amount of sharing can shave off the exponential growth.

```
# let pair x f = f x x;;
# let f1 x = pair x in
  let f2 x = f1 (f1 x) in
  let f3 x = f2 (f2 x) in
  fun z -> f3 (fun x -> x) z;;

```

### References

\[KTU90\] Kfoury, J.; Tiuryn; Urzyczyn, P. (1990). "ML typability is dexptime-complete". Lecture Notes in Computer Science. CAAP '90 431: 206-220. \[Springer\] \[Google\]

\[M90\] Mairson, Harry G. (1990). "Deciding ML typability is complete for deterministic exponential time". Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL '90 (ACM): 382–401. \[ACM\]

\[P04\] Benjamin C. Pierce. Advanced Topics in Types and Programming Languages. MIT Press, 2004. \[Amazon\]

\[PR04\] François Pottier and Didier Rémy. "The Essence of ML Type Inference". Chapter 10 in \[P04\]. \[pdf\]

\[S95\] Michael I. Schwartzbach. Polymorphic Type Inference. BRICS LS-95-3, June 1995. ps

---
Tags: lambda-calculus, type-theory, functional-programming, type-inference, type-checking
---


# Question
Title: When can a greedy algorithm solve the coin change problem?
Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v.

E.g. for the coinset 1,5,10,20 this gives 2 coins for the sum 6 and 6 coins for the sum 19.

My main question is: when can a greedy strategy be used to solve this problem?

---

Bonus points: Is this statement plain incorrect? (From: How to tell if greedy algorithm suffices for the minimum coin change problem?)

> However, this paper has a proof that if the greedy algorithm works for the first largest denom + second largest denom values, then it works for them all, and it suggests just using the greedy algorithm vs the optimal DP algorithm to check it. http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. note that the answers in that thread are incredibly crummy- that is why I asked the question anew.

# Answer
> 15 votes
A coin system is *canonical* if the number of coins given in change by the greedy algorithm is optimal for all amounts.

The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system is canonical, where $n$ is the number of different kinds of coins. From the abstract:

> We then derive a set of $O(n^2)$ possible values which must contain the smallest counterexample. Each can be tested with $O(n)$ arithmetic operations, giving us an $O(n^3)$ algorithm.

The paper is quite short.

For a non-canonical coin system, there is an amount $c$ for which the greedy algorithm produces a suboptimal number of coins; $c$ is called a *counterexample*. A coin system is *tight* if its smallest counterexample is larger than the largest single coin.

The paper Canonical Coin Systems for Change-Making Problems provides necessary and sufficient conditions for coin systems of up to five coins to be canonical, and an $O(n^2)$ algorithm for deciding whether a tight coin system of $n$ coins is canonical.

There is also some discussion in this se.math question.

---
Tags: algorithms, combinatorics, greedy-algorithms
---


# Question
Title: Implementing addition for a binary counter
A binary counter is represented by an infinite array of 0 and 1.

I need to implement the action $\text{add}(k)$ which adds $k$ to the value represented in the array.

The obvious way is to add 1, k times. Is there a more efficient way?

# Answer
Well, surely there is.

As a first thing I would convert $k$ to its binary representation $\text{bin}(k)$. If $c$ is the current value of your counter then in order to perform $\text{add}(k)$ just update the counter by setting it to $\text{bin}(c)+\text{bin}(k)$.

If you don't know how to add binary numbers efficiently, think how you would have done it using pen and paper.

For small $k\in O(\log c)$ the repeated increment might be efficient though.
> 3 votes

---
Tags: algorithms, data-structures, efficiency
---


# Question
Title: How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?
How do I show that the problem of deciding whether a PDA accepts some string of the form $\\{ w!w \mid w \in \\{ 0, 1 \\}^\*\\}$ is undecidable?

I have tried to reduce this problem to another undecidable one such as whether two context-free grammars accept the same language. However, I'm not sure how to use it as a subroutine.

# Answer
Here is my approach: I'll show that if you can decide your problem, then you can decide Post's correspondence problem (PCP), which is known to be not decidable.

Remember, PCP is a decision problem that asks if in a set of $2$-tuples $P=\\{(x\_1,y\_1),\ldots,(x\_n,y\_n)\\}$ you can build a sequence (incl. repetition) such that the concatenated $x\_i$s and the concatenated $y\_i$s of this sequence form the same word. Notice that the alphabet has to have at least 2 characters.

So, let $P$ be an instance of the PCP. Consider the following context-free grammar, where we've introduced a new terminal symbol $t\_i$ for the $i$-th element in $P$. The grammar has the following rules: $$ \begin{align} S& \to X \\; ! \\;Y \\ X& \to x\_1 X' t\_1 \mid x\_2 X' t\_2 \mid \cdots x\_n X' t\_n \\ X'& \to x\_1 X' t\_1 \mid x\_2 X' t\_2 \mid \cdots x\_n X' t\_n \mid \varepsilon\\ Y& \to y\_1 Y t\_1 \mid y\_2 Y t\_2 \mid \cdots y\_n Y t\_n \mid \varepsilon \\ \end{align} $$ (The variable $X'$ is only there to rule out $S\Rightarrow !$).

Of course, given any grammar, we can find a corresponding PDA that accepts the same language as the grammar. So, construct the corresponding PDA, and then use the hypothetical algorithm for your problem to determine whether this PDA accepts any word of the form $u!v$ (i.e., whether one can derive any word of the form $u!v$ from this grammar). I will show how to use this information to solve the PCP instance $P$.

Assume now that $u!v$ is a word in this grammar. The word $u$ has two parts, the suffix, consisting of the $t\_i$ terminals, and the remainder called prefix. The same is true of $v$. We have $u=v$ if and only if their prefixes and suffixes coincide. The suffixes coincide only if we have used the same sequence of tuples from $P$ to built the words $u$ and $v$. The prefixes of $u$ and $v$ coincide if the concatenation of the $x\_i$s and $y\_i$s (based on the reversed tuple-sequence given by the $t\_i$s) is the same. Hence $u=v$ if and only if there is a solution for the PCP instance $P$.

Similarly, if there is a solution for the PCP instance $P$, then from the solution it is easy to construct a word of the form $u!v$ that is derivable from this grammar.

It follows that the PCP instance $P$ has a solution if and only if this grammar contains a word of the form $u!v$. If there was an algorithm to decide your problem, we could use it to solve PCP. But of course PCP is known to be undecidable, so your problem is undecidable, too.
> 12 votes

# Answer
The approach might be as follows. Try to make a context-free (=PDA) language that codes computation steps of a TM, such that the complete computation is successful iff there is a word of the form you describe.

First you need to code separate configurations: tape contents + state + position head (you will have seen that for grammar equivalence). A context-free language can encode a single step $C\vdash C'$ of a computatation provided you use mirror image $C\\#m(C')$, where $m(C)$ denotes the mirror image (reversal) of $$C$. (I am sloppy here: you may have to distinguish configuration and its description.)

Now consider the language of separate steps, concatenated with the language of duplicated configurations: $C\_0\\#C\_1\\#m(C\_2)\\#C\_3\\#m(C\_4)\\# \dots C\_{2n-1}\\#m(C\_{2n})\\#C\_f!$ $C'\_1\\#m(C'\_1)\\#C'\_2\\#m(C'\_2)\\#\dots C'\_{n+1}\\#m(C'\_{n+1})$ with for every $k$, $C\_{2k-1} \vdash (C\_{2k})$. This is context-free, additionally code $C\_0$ as initial and $C\_f$ as final configurations.

Now the first part ensures we have consecutive steps, the second part that successive configurations are equal. If both parts match we have a computation. Which we cannot decide.

That is the idea. I may have some indexes wrong, *and* the whole sequence has to be encoded in binary, but that can be solved.
> 6 votes

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


# Question
Title: How to implement a Prolog interpreter in a purely functional language?
Is there a clear reference, with pseudo-code, on how to go about implementing a Prolog interpreter in a purely functional language? That which I have found so far seems to deal only with imperative languages, is merely a demonstration of Prolog implemented in itself, or offers no concrete algorithm to use for interpretation. I would be very appreciative of an answer.

# Answer
Since Prolog = Syntactic Unification \+ Backward chaining \+ REPL

All three parts can be found in Artificial intelligence: structures and strategies for complex problem solving by George F. Luger. In the fourth edition of the book all three parts are implemented in LISP in Section 15.8, Logic Programming in LISP. He also puts the same code in his other books, but I don't have all of them for noting here. The code for his books can be found here.

Another source with all three parts can be found in Paradigms of artificial intelligence programming: case studies in Common Lisp by Peter Norvig. See Chapters 11, Logic Programming and 12, Compiling Logic Programs. The code for his book can be found here.

Another source is Structure and interpretation of computer programs by Hal Abelson, Jerry Sussman and Julie Sussman. See Section 4.4 Logic Programming. The site for the book is here and the code for the book is here.

It is not uncommon to find the unification algorithm with back chaining implemented in many applications if you know where to look; it is especially prevalent in type inferencing in functional compilers. Using the keywords unification or occurs helps to spot the functions. Also most implementations use unif for the name of the unification function.

For a version of Prolog, less the REPL, done in OCaml see Code and resources for "Handbook of Practical Logic and Automated Reasoning" \- prolog.ml

A translation of the book code to F# can be found here. A translation of the book code to Haskell can be found here.

In terms of finding the code, the unification algorithm is easiest to find, then implementations with back chaining imbedded in applications. Finding a fully functional implementation of Prolog in a functional language with an REPL is the hardest. Most of the time the code is not in a format for direct use within PROLOG; it is heavily customized to enhance performance, so you may find the code but it will not be worth the price to tease out the parts you want. My advice would be to read Luger's book and build it up from scratch in your language of choice, even if it means installing and learning LISP and translating to do so.

EDIT

Since this is a duplicate question from StackOverflow and the OP is new and in the comments says:

> To give more context, I'm attempting to implement type inference, however the intricate features in the type system of my language (Dependent types, refinement types, linear typing to name a few of the less common ones) make me feel that it would be useful to base my type inference off of the algorithms driving Prolog as to obtain a very general algorithm. I will note that I'm entirely self taught, so my knowledge is lacking in large areas.

I'll expand on this here, but realize the OP should ask a new question.

For some intro stuff see implementing type inference.

The best book I know on this is Types and programming languages by Benjamin C. Pierce. The book's site is here. The resources with links to OCaml code is here. And recently started but mostly complete translation of this to F# is here.

Dependent types: pg. 462 Refinement types: pg. 207 Linear logic and type systems: pg. 109
> 25 votes

# Answer
See the implementation of miniprolog at my Programming languages zoo, it is the last one on the list. You can see source code online, the code is well documented.
> 13 votes

---
Tags: functional-programming, prolog, logic-programming
---


title: Greedy algorithms tutorial

text:
# Question
Title: Greedy algorithms tutorial
Could anyone point me to simple tutorial on greedy algorithm for Minimum Spanning tree - Kruskal's and Prims' Method

I am looking for a tutorial which

* does not include all the mathematical notation
* explains algorithm along with the analysis of the running time.

# Answer
Here is a simple definition for greedy algorithm.

There are many greedy algorithms for different problems and in order to understand them you must also know well the subject of the problem. This question on stackoverflow gives some examples of greedy algorithms usage.

EDIT : After you made your question more clear I will try to sketch the algorithms by using "minimum mathematical notation". Both the Kruskal's and Prim's algorithms build MST in connected graph.

Let we have graph G with vertices V and edges E.

**Prim's algorithm**

1. Select some vertex r from V and add it to the tree. r will be the root of the tree
2. Until all vertexes V are in the tree :

Find the shortest edge from E that has one end in the already constructed tree and the other in some of the vertices of the graph that are not in the tree and add the edge and the new vertex to the tree
3. When the condition in step 2. is not correct you will have the MST constructed

**Kruskal's algorithm**

1. Construct forest of trees where each tree is a single vertex from V
2. Until all trees are connected into single one :

Find the shortest edge from E that connects two unconnected trees and connect them with it. That step constructs from two trees a new one.
3. When the condition in step 2. is not correct all the trees will be connected into single one that is the MST

Note: After each iteration we have a tree/trees because there is no way to add a edge that forms a cycle

Note: The tree consists of vertexes and edges (it is kind of graph). When adding a vertex to the tree we add it to the set of vertices and when adding edge - to the set of edges.

**Running Time**

This part really **needs mathematical notation and depends on specifics in the implementation** of the algorithms, so I will leave it only with some answers and links to Wikipedia,where there are some general explanations.

Prim's Algorithm = O(E.log E) = O(E. log V)

Kruskal's Algorithm = O(E.log E) = O(E. log V)

Please read the explanations and ask only the things that are unclear to you(maybe in different question if they are related to the asymptotic notations)

**"Greedy Part"**

The greedy part in both of the algorithms is choosing to add the shortest edge to the tree. The **shortest** edge is the logically optimal choice when constructing **Minimal** Spanning Trees.
> 7 votes

---
Tags: algorithm-analysis, greedy-algorithms
---


title: Memoized Palindrome Subsequence

text:
# Question
Title: Memoized Palindrome Subsequence
I am trying to find the maximum palindrome sub-sequence and after going through some tutorials, I came up with a memoized version.But I am not sure about the runtime.I want to know if the following algorithm will work.Could also someone explain what the runtime will be?

```
Memoized-Palindrome(A,n)
initialize longest [i][j] =0 for all i and j
then return Memoized-Palindrome1(A,1,n,longest)

Memoized-Palindrome1(A,i,j,longest)
if longest[i][j]>0 return longest [i][j]
if (j-i) <=1 return j-i
if A[i]==A[j]
      then longest[i][j] = 2 + Memoized-Palindrome1(A,i+1,j-1,longest)
    else
      longest[i][j]= max(Memoized-Palindrome1(A,i+1,j,longest),Memoized-Palindrome1(A,i,j+1,longest)
return longest[i][j]

```

# Answer
This kind of approach is more often called dynamic programming than memoization but they are, indeed, related.

In dynamic programming, however, you usually write the order in which your function is called. (This is one key difference between them.) In this case, you will clearly see that you will compute $n$ `longest[i][i]` first, then $n-1$ `longest[i][i+1]`, then $n-2$ `longest[i][i+2]` etc. each computation being in constant time. Giving a complexity of $n+(n-1)+\dots+2+1$=$n(n+1)/2$ i.e. $O(n^2)$.
> 1 votes

---
Tags: algorithm-analysis, dynamic-programming, memoization
---


# Question
Title: Counting sort on non-integers - why not possible?
What is it about the structure of counting sort that only makes it work on integers?

Surely strings can be counted?

```
''' allocate an array Count[0..k] ; initialize each array cell to zero ; THEN '''
for each input item x:
    Count[key(x)] = Count[key(x)] + 1
total = 0
for i = 0, 1, ... k:
    c = Count[i]
    Count[i] = total
    total = total + c

''' allocate an output array Output[0..n-1] ; THEN '''
for each input item x:
    store x in Output[Count[key(x)]]
    Count[key(x)] = Count[key(x)] + 1
return Output

```

Where above does the linear time break down if you try to use counting sort on strings instead (assuming you have strings of fixed length)?

# Answer
> 17 votes
If you naively apply the algorithm you need an encoding $f$ of strings of length $m$ into integers such that $s\_1≤s\_2$ iff $f(s\_1)≤f(s\_2)$. The bound on these integers is necessarily at least $c^m$ where $c$ is the number of possible characters.

You then have a complexity in $O(nc^m)$ where $n$ is the number of elements to be sorted. This could be interesting when $c^m$ is not too big compared to the usual bound $\log n$, which is possible, in very peculiar cases.

In general, one would prefer the bound $O(n\log n)$ which does not depend on the length of your strings and in general much faster than $O(nc^m)$. To give a formal comparison between them, the former would be $O(s\log s)$ and the latter $O(sc^s)$ where $s$ is the size of the input.

However what is possible if you know that you will have a number of different strings no greater than some $k$, and that there will be a lot of occurrences of the same strings, is to build a correspondence between these strings and $\\{1,\dots,k\\}$ on which you will apply the counting sort, thus obtaining a complexity of $O(kn)$ i.e. linear (since $k$ is constant). But in this case the counting sort is not the only one reaching a linear complexity, for example all algorithms using balanced trees can be adapted to be linear, even insertion sort which is quadratic in the worst case, becomes linear.

---
Tags: algorithms, sorting
---


# Question
Title: Are two terms where one is without a $\lambda\beta$ normal form unconvertible in $\lambda\beta$?
I know that if you try and make the theory

$$\lambda\beta+\\{s = t\ |\text{ s, t are terms without }\lambda\beta\text{ normal forms}\\}$$

then that theory becomes inconsistent. Are two terms where one is without a $\lambda\beta$ normal form also unconvertible in $\lambda\beta$, ie can it ever be true that $\lambda\beta \vdash s=t$ if $s$ dosen't have a normal form?

# Answer
> 2 votes
It is trivially the case that two terms can be $\beta$-convertible even though they do not have a normal form.

Consider:

$$((\lambda x.x)\ (\lambda x.x\ x))\ (\lambda x.x\ x)$$

and

$$(\lambda x.x\ x)\ (\lambda x.x\ x).$$

In one step we have $$((\lambda x.x)\ (\lambda x.x\ x))\ (\lambda x.x\ x)\to (\lambda x.x\ x)\ (\lambda x.x\ x)$$

---
Tags: terminology, logic, lambda-calculus
---


# Question
Title: When do structural hazards occur in pipelined architectures?
I'm looking for some relatively simple examples of when structural hazards occur in a pipelined architecture.

The only scenario I can think of is when memory needs to be accessed during different stages of the pipeline (ie, the initial instruction fetch stage and the later memory read/write stage).

I'm thinking that there are many more structural hazards in more complex architectures, such as superscalar. Does it class as a structural hazard when an instruction is dispatched to an execution unit but is queued because the unit is in use?

If this is highly architecture-specific, then just assume MIPS or something similar.

# Answer
> 6 votes
In a scalar implementation, a structural hazard can exist if specific execution hardware is not fully pipelined. For some operations (e.g., multiplication and especially division) the cost of implementing full pipelining may not be considered worthwhile for the expected frequency of the operation.

In a superscalar implementation, a structural hazard may exist because not every execution unit can perform every operation. E.g., supporting initiating execution of four memory operations or four multiplications every cycle would be relatively expensive when limited to four-wide issue given that a different type of operation is likely to be available.

Register file read and write port limits can also introduce structural hazards. Although it is possible to provide enough read and write ports to support the worst case, the costs of register file ports to satisfy the worst case (even with the benefit in design complexity of not having to specially handle exceptional cases) can be considered not worth the benefits when the bad cases are sufficiently rare or non-critical. E.g., some out-of-order implementations use operand capture (grabbing operands that become available between the time the operation enters the scheduler and the time it is scheduled for execution) and provide fewer register read ports than required for full width operation (whether operands available earlier are read when the operation enters the scheduler or when the operation is scheduled for execution).

(Even for an in-order implementation, result-forwarding and the use of operations with a single register source operand could make supporting four register read ports for two-way issue less necessary.)

Similarly, banking is often used for caches (and has been proposed for register files). E.g., in the common case, two accesses are unlikely to map to the same bank out of 16 banks. Banking storage is substantially less expensive than adding access ports. The potential for bank conflicts represents a structural hazard.

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


# Question
Title: Proving that NPSPACE $\subseteq$ EXPTIME
I am following **"Introduction to the theory of computation" by Sipser**.

My question is about relationship of different classes which is present in **Chapter 8.2. The Class PSPACE**.

$P \subseteq NP \subseteq PSPACE = NPSPACE \subseteq EXPTIME$

I am trying to understand why the the following part is true $NPSPACE \subseteq EXPTIME$.

The explanation from the textbook is following:

*"For $f(x)\geq n$, a TM that uses $f(x)$ space can have at most $f(n)2^{O(f(n))}$ different configurations, by a simple generalization of the proof of the Lemma 5.8 on page 194. A TM computation that halts may not repeat a configuration. Therefore a TM that uses space $f(n)$ must run in time $f(n)2^{O(f(n))}$, so $NPSPACE \subseteq EXPTIME$"*

I am trying to understand why it's true, why TM that uses $f(n)$ space must run in time $f(n)2^{O(f(n))}$. Let's try to reverseengeneer the formula: $n$ is the length of the input, 2 is the size of alphabet, $f(n)$ is the space that TM use on the second tape (operational tape) and $f(n) \geq n$, but how to explain what $O(f(n))$ means. Apparently, $2^{O(f(n))}$ expreses a configuration, so $O(f(n))$ must express union of transition function and alphabet, but actually it seems like I get it wrong. The most intriguing question why, in the end, $f(n)2^{O(f(n))}$ expressed in the terms of time, the transition from space to time is very vague for me.

I will very appreciate if someone could explain me this relationship.

# Answer
> 10 votes
The expression $f(n)2^{O(f(n))}$ is simply an upper bound for the number of all configurations a $f(n)$-space bounded TM can have. Here is how to count: We have $|\Gamma|^{f(n)}=2^{O(f(n)}$ different ways how to fill the work tape, and the head can be on $f(n)$ different positions. There is also a constant number of states where we can currently be, but this is hidden in the big-O in the exponent.

If a TM takes more than $f(n)2^{O(f(n))}$ steps, then it has to visit one configuration twice. Hence it cycles and cannot stop.

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


# Question
Title: Which kind of branch prediction is more important?
I have observed that there are two different types of states in branch prediction.

1. In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay.
2. In the instruction pipeline, where the fetching is more problem since the instructions do not actually get executed till later.

Which of these is very important (as in which of these really matters in the CPU now-a-days)? If both are equally important or in case the second one is more important then Why do we not have two instruction pipeline (probably of half the length ) and then depending on the branches, just choose one of them and then again start the population from the beginning?

# Answer
I don't know which case is prevalent, but I would like to offer some thoughts on your proposal of double pipelines.

First of all, you would need double the wire which would consume double the energy and produce double the heat while active. While not needed, on the other hand, it would be completely useless. So one could argue that it is not a good use of resources that are rare on modern processors.

More fundamentally, unless you prefer one branch based on probability, how do you know which version to write through? If none, you might not save anything because other processors might have to wait on your decision, anyways. If you stick with one of them, you have essentially the same rollback probability and cost as you have now.

Let us do a rough calculation. For sake of simplicity, let us assume that handling two pipelines instead of one does not cause additional management overhead. The expected cost (e.g. energy, heat) is $C = c + p(c\_r + c)$ with one pipeline ($c$ the cost of executing either alternative, $p$ the probability for rollback and $c\_r$ the cost for rollback without the cost for executing the other alternative) but either $2c$ or even $2c + pc\_r$ -- either is *a lot* larger than $C$ if $p$ and $c\_r$ are relatively small, and $p$ certainly is (as far as I know, modern branch predictions have accuracies over 90%). And we don't get much for this cost! Expected execution times are $t + p(t\_r + t)$ with one pipeline and $t$ resp. $t + pt\_r$ with two; as $p$ is small, time savings are negligible.
> 6 votes

# Answer
In one sense, the effect of branch prediction is more critical in the fetching of instructions since an instruction which is not fetched cannot be executed.

With respect to executing both paths of a branch, this is called eager execution and has been researched somewhat substantially. Augustus K. Uht and Vijay Sindagi's "Disjoint Eager Execution: An Optimal Form of Speculative Execution" (1995) might be a worth a look.

Eager execution has several problems. For deep speculation, the number of paths that must be tracked can grow exponentially (each forked branch path may encounter a branch). Branch prediction is also often very accurate (\>90% correct), so always executing both paths would be wasteful. Eager execution can also "contaminate" caches with useless content. (The above mentioned paper proposed *intelligently limited* eager execution to avoid some of these issues.) Limited eager fetching the alternate path has fewer issues and can be somewhat attractive in reducing misprediction recovery delay in shorter pipelines.

Another approach that has been proposed is dynamically predicating "hammock" branches (short forward branches that join back to the main path of instruction flow). Artur Klauser et al.'s "Dynamic Hammock Predication for Non-predicated Instruction Set Architectures" (1998) might be worth a read for that idea. (Hyesoon Kim et al.'s "Wish Branches: Combining Conditional Branching and Predication for Adaptive Predicated Execution" proposes adding to an ISA branches which facilitate predication of hammocks and extends this method of predication to hard-to-predict loop branches.)
> 2 votes

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


# Question
Title: Is $\{a^nb^m \mid n,m\ge 0, n\ne m\}$ regular or not?
> **Possible Duplicate:**
> Prove that the complement of $\\{0^n1^n \mid n \geq{} 0\\}$ is not regular using closure properties

Is $L=\\{ a^nb^m \mid n,m \ge 0, n\ne m\\}$ a regular language?

I think it is but can't prove it.

# Answer
> 4 votes
Using Ran G.'s comment which links to a very similar question:

Suppose $L$ is regular. $M=a^\*b^\*$ is regular, too, so since regularity is closed by set difference, $M\backslash L=\\{a^nb^n\\}$ would be, too, which is the usual counterexample.

# Answer
> 0 votes
The comment of Patrick87 correctly points out the flaw in my "proof" below, but I let it be as it were as it might be a good starting point. Together with his comment, it should be simple to prove that the language is not regular.

First you should know that a language $L$ is regular if and only if its complement is regular. This is fairly simple to prove, given a deterministic finite automaton $M$, let $M^{-1}$ be the automaton where a state is accepting if and only if it is not accepting in $M$.

Given this theorem you should be able to prove that since $L$ is the complement of the classic non-regular language, $L$ is not regular either.

*(Handwaving: A language is usually not regular if you need to count stuff in a word to determine whether or not a word belongs to the language. You can, for any constant $k$ count stuff with respect to $k$, like modulo, $\leq$ etc, but in your example you need to be able to count to $m$ and $n$ for any $n$ and $m$.)*

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


title: Intuition behind Relativization

text:
# Question
Title: Intuition behind Relativization
I take course on Computational Complexity. My problem is I don't understand **Relativization method**. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will appreciate if someone could shed the light on this topic so that I will be able to continue by myself. Few following sentences are questions and my thoughts about relativization, they will help to navigate the discussion.

Very often relativization comes in comparison with diagonalization, which is a method that helps distinguish between countable set and uncountable set. It somehow comes from relativization that $P$ versus $NP$ question cannot be solved by diagonalization. I don't really see the idea why relativization show the useless of diagonalization, and if it's useless why is actually useless.

The idea behind oracle Turing machine $M^A$ at first is very clear. However, when it comes to $NP^A$ and $P^A$ the intuition disappears. Oracle is a blackbox that is designed for special language and answers the question whether the string on the input of the oracle is in the language in time 1. As I understood TM that contains an oracle is just make some auxiliary operations and ask the oracle. So the core of the TM is the oracle, everything else is less important. What's the difference between $P^A$ and $NP^A$, even thought oracle in both of them works in time 1.

The last thing is the proving the existence of an oracle $B$ such that $P^B \neq NP^B$. I found the proof in several textbooks and in all of them the proof seems very vague. I tried to use **"Introduction to complexity" by Sipser, Chapter9. Intractability**, and didn't get the idea of construction of a list of all polynomial time oracle TMs $M\_i$.

This is more or less everything what I know about relativization, I will appreciate if someonw would decide to share his/her thoughts on the topic.

**Addendum**: in one of the textbooks I found example of $NP^B$ language (Computational Complexity: A Modern Approach by Boaz Barak Sanjeev Arora. Theorem 3.7. Page 74). $U\_B=\left \\{ 1^n:some \space string \space of \space length \space n \space is \space in \space B\right \\} $ it's unary language. I believe that (1,11,111,1111,...) are all in $U\_B$. Author affirms that such a language is in $NP^B$ which is I cannot understand why, hence oracle for B can resolve everything in time 1. Why do we need nondeterministic TM with oracle. If it's not good example of $NP^B$ please put yours such that to approve the existence of $NP^B$.

# Answer
> 7 votes
You haven't really asked any question, but it seems like you don't know what $\rm{P}^A$ means and what $\rm{NP}^A$ means for a language $A$. The class $\rm{NP}^A$ is simply all languages that are decidable in "NP time", given a turing machine with $A$ as an oracle. This means a non-deterministic turing machine with access to $A$ which runs in polynomial time. The $\rm{P}^A$ is the deterministic version.

---
Tags: complexity-theory, np-complete, complexity-classes, relativization, np
---


# Question
Title: Reduction from 3-Partition problem to Balanced Partition problem
The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks whether $2n$ integers can be partitioned into two equal cardinality sets such that both sets have the same sum. Both problems are known to be NP-complete. However, 3-Partition is strongly NP-complete. I haven't seen in the literature any reduction from 3-Partition to Balanced Partition.

I'm looking for (simple) reduction from the 3-Partition to the Balanced Partition problem.

# Answer
> 2 votes
There are thousands of NP-complete problems in the literature, and most pairs do not have explicit reductions. Since polynomial-time many-one reductions compose, it suffices for researchers to stop when the graph of published reductions is strongly connected, making research into NP-completeness a much more scalable activity.

Although I really don't see the point, I'll humor you by giving a reasonably simple reduction from 3-PARTITION to BALANCED PARTITION, with a few hints about how the proof of correctness goes.

Let the input to the reduction be $x\_1, \ldots, x\_{3n}, B \in \mathbb Z$, an instance of 3-PARTITION. Verify that $\sum\_{i\in\[3n\]} x\_i = nB$. Let $\beta$ be a large number to be chosen later. For every $i \in \[3n\]$ and every $j \in \[n\]$, output two numbers $$x\_i \beta^j + \beta^{n+j} + \beta^{2n+i} + \beta^{(i+4)n+j}\\ \beta^{(i+4)n+j}.$$ Intuitively, the first number means that $x\_i$ is assigned to 3-partition $j$, and the second number means the opposite. The $x\_i \beta^j$ term is used to track the sum of 3-partition $j$. The $\beta^{n+j}$ term is used to track the cardinality of 3-partition $j$. The $\beta^{2n+i}$ term is used to ensure that each $x\_i$ is assigned exactly once. The $\beta^{(i+4)n+j}$ term is used to force these numbers into different balanced partitions.

Output two more numbers $$1 + \sum\_{j\in\[n\]} \Bigl((n-2)B\beta^j + (3n-6)\beta^{n+j}\Bigr) + \sum\_{i\in\[3n\]} (n-2)\beta^{2n+i}\\ 1.$$ The first number identifies its balanced partition as “true”, and the other, as “false”. The $1$ term is used to force these numbers into different balanced partitions. The other terms make up the difference between the sum of a 3-partition and the sum of its complement and the size of a 3-partition and the size of its complement and the number of times $x\_i$ is assigned.

$\beta$ should be chosen large enough to ensure that “overflow” cannot occur.

# Answer
> 0 votes
This paper, Fast Balanced Partitioning is Hard Even on Grids and Trees, by Andreas Emil Feldmann contains what you want! Good luck!

> We will set up a general framework for a reduction from 3-PARTITION to different graph classes. This will be achieved by identifying some structural properties that a graph constructed from a 3-PARTITION instance has to fulfil, in order to show the hardness of the $k$-BALANCED PARTITIONING problem ...

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


# Question
Title: Prove multiple cell move instructions don't increase power of Turing Machines
How can you prove that multiple-cell-move instructions, for example (X, Y, 5R) and (X, Y, 17L), do not increase the power of a Turing Machine?

# Answer
> 9 votes
A quick answer: the control of every TM is finite, so given a TM $M$, the jumps in its transition table are finite. Suppose that it has the following jump transition:

```
on state_x: if read symbol a -> write b, jump 3R, goto state_y

```

then you can simulate it using 3 *single step* transitions :

```
on state_x: if read symbol a  -> write b, move R, goto state_x2
on state_x2: if read symbol <anysymbol> -> write <anysymbol>, move R, goto state_x3
on state_x3: if read symbol <anysymbol> -> write <anysymbol>, move R, goto state_y

```

In general if $len$ is the length of the jump of a transition, you can simulate it adding $len-1$ new states to $M$ and the new states are used simply to move the head for $len-1$ more steps and finally enter the same target state of the original jump transition.

To be pedantic, you need to add additional states only for distinct triples (jump length, jump direction, target state). For example if a transition has (jump 5, right, and goto state z) the added single step states can be reused on every transition with the same value of jump length, jump direction and target state.

---
Tags: turing-machines
---