# Question
Title: polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$
If we have two languages $L\_{1} \subseteq \Sigma^{\ast}\_{1}$ and $L\_{2} \subseteq \Sigma^{\ast}\_{2}$

I proved that when $L\_{2} \in \textbf{P}$ and $L\_{1} \leq\_{p} L\_{2}$ then $L\_{1} \in \textbf{P}$

Is it also true that when $L\_{2} \notin \textbf{P}$ and $L\_{1} \leq\_{p} L\_{2}$ then $L\_{1} \notin \textbf{P}$? I don't think it's, but I can't find a counter-example.

# Answer
> 0 votes
Let $L\_1=\emptyset$ and $L\_2=\\{\langle M\rangle\mid M\text{ halts on empty string}\\}$. Let $s$ be a string that does not belong to $L\_2$, for example, the empty string, which is a string that does not even represent a Turing machine. The reduction $f$ is $\forall x, f(x)=s$.

Now you can see $L\_1\in\mathbf{P}$ and $L\_2\notin\mathbf{P}$ (in fact, $L\_2$ is undecidable), and $f$ is a polynomial-time reduction (it just ignores the input and outputs $s$ directly). Also, $x\in L\_1\Leftrightarrow f(x)\in L\_2$ (note $x$ always $\notin$ $L\_1$ and $f(x)=s$ always $\notin$ $L\_2$).

This is a counter-example.

---
Tags: formal-languages, reductions, polynomial-time
---


# Question
Title: Egg dropping puzzle - clarification of problem statement
I was trying to understand the egg dropping puzzle. The problem objective is:

What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the **worst case** for the number of drops it will take?)

I understand we want to minimize the egg drops, but what does this **worst case** number of drops infer to. This makes me more confuse. Can anyone explain its meaning.

# Answer
> 1 votes
Imagine this as a game of two players: the experimenter vs. nature.

The egg breaking limit is not chosen in advance. Instead, the players together form statements about its possible values, all the way until only one value remains.

On each turn, the experimenter chooses the floor from which to drop the egg. After that, the nature chooses whether the egg actually breaks or not.

Of course, with some moves of the experimenter, nature can't choose because the previous statements already determine the outcome. However, note that a good strategy for the experimenter does not make such redundant moves.

With such formulation, the "worst case" here is equivalent to the game-theoretic "if nature plays optimally", and "minimizing the number of moves in the worst case" to "if both play optimally".

---
Tags: algorithms, dynamic-programming
---


title: Decidability of L

text:
# Question
Title: Decidability of L
I have the following problem. If L is decidable and L = L1 u L2 (union). So are L1 and L2 decidable, too?

I know that, if L is decidable, the complement is also. And this means the complement is recursively enumerable. How can I proof it?

# Answer
> 6 votes
Let $L\_1$ be the halting problem and $L\_2 = \overline{L\_1}$. The union of $L\_1$ and $L\_2$ is $\Sigma^\*$, which is decidable, while $L\_1$ and $L\_2$ are not.

---
Tags: complexity-theory, computability
---


# Question
Title: Calculating decimal digits of pi, using something similar to a Bailey–Borwein–Plouffe formula
I have tried to Use the Bailey–Borwein–Plouffe formula to calculate pi to 3 digits as a test trial, and recieved the digit 4, which is technically correct, as 4 is the 3rd digit of pi in base 16. I would like to get the digit in decimal, as that is the current standard for numbering things in most places, as you don's see many things labelled D5 except in excel spreadsheets. Basically, I need to conduct a Bailey–Borwein–Plouffe formula from 0-6 (intead of 0 - infinity as i only need pi to 6 digits), but in decimal.

Here is what I had for the base 16 computation.

```
double pi2 = 0;
int n = 0;
while (n < 3)
{
    double a = (1/(Math.pow(16, n)));
    double b = (4/((8*n) + 1));
    double c = (2/((8*n) + 4));
    double d = (1/((8*n) + 5));
    double e = (1/((8*n) + 6));
    pi2 += a*( b - c - d - e );
    n++;
}

```

# Answer
The Bailey–Borwein–Plouffe formula only works in hexadecimal. There might be other formulas for other bases, but I'm not aware of a decimal-based formula. If you want to obtain the $N$th decimal digit, you have to compute enough hexadecimal digits, there are no shortcuts.
> 5 votes

# Answer
Your problem is you are trying to multiply a double with an integer value, which will result in an integer result being stored in a double. If you cast n to a double then you should get the desired result.

ie:

```
double b = (4 / ((8 * (double)n) + 1));
double c = (2 / ((8 * (double)n) + 4));
double d = (1 / ((8 * (double)n) + 5));
double e = (1 / ((8 * (double)n) + 6));

```

With your current code, c,d and e are always 0 because you're losing your double's accuracy, it will always be rounded down to 0. b only ever has a value on the first cycle because 4/1 is a nice whole number.

Hope that helps.
> 1 votes

# Answer
These two links show how you can integrate the base-changing formula into the digit calculation formula, to directly calculate the nth decimal digit of pi. They don't appear to be very simple!

http://lacim.uqam.ca/~plouffe/Simon/articlepi.html

https://bellard.org/pi/

There are other older algorithms that compute the nth decimal digit of pi, but they have to compute all the digits before the nth digit. These are the 'spigot algorithms'

https://www.cut-the-knot.org/Curriculum/Algorithms/SpigotForPi.shtml

http://www.stanleyrabinowitz.com/bibliography/spigot.pdf

https://en.wikipedia.org/wiki/Spigot\_algorithm

The Rabinovitz and Wagon algorithm is roughly 20 lines of pseudo code
> 1 votes

---
Tags: algorithms, numerical-algorithms
---


# Question
Title: Defining an HTML Template as an Algebraic Type
Wondering if/how you could define a highly nested structure as a Dependent Type (or an Algebraic or Parameterized type). Specifically, an HTML template. Not that they work like this (HTML templates don't have variables to plug in), but imagine a template like this:

```
<template id="MyTemplate">
  <section>
    <header>
      <h1>{title}</h1>
      <h2>{subtitle}</h2>
    </header>
    <div>{content}</div>
    <footer>
      <cite>{author}</cite>
      <time>{year}</time>
    </footer>
  </section>
</template>

```

This is a template, so it basically acts like a class (or a *type*). So you would instantiate the type like this:

```
var node = new MyTemplate({
  title: 'A title',
  subtitle: 'A subtitle',
  content: 'Foo bar ...',
  author: 'foo@example',
  year: 2018
})

```

And you would get:

```
<section>
  <header>
    <h1>A title</h1>
    <h2>A subtitle</h2>
  </header>
  <div>Foo bar ...</div>
  <footer>
    <cite>foo@example</cite>
    <time>2018</time>
  </footer>
</section>

```

The HTML *node* that is returned is like the type instance. (I'm assuming these are HTMLEntity objects and related DOM objects, not strings). The way the DOM node *instances* are generically represented is:

```
{
  tag: 'section',
  children: [
    {
      tag: 'header',
      children: [ ... ]
    },
    ...
  ]
}

```

But the template, being a type, is like it is defining multiple nested types at once. That is, this is a type:

```
<h1>{title}</h1>

```

And that is wrapped in this type:

```
<header>
  <h1>{title}</h1>
  <h2>{subtitle}</h2>
</header>

```

And that is wrapped in the `<section>...</section>` type. It's like a type like this:

```
type Section {
  type Header {
    type H1 {
      title: String
    }
    type H2 {
      subtitle: String
    }
  },
  type Div {
    content: String
  },
  type Footer {
    type H1 {
      cite: String
    }
    type H2 {
      time: Integer
    }
  }
}

```

Or perhaps, since we are actually plugging this into the HTMLEntity's `textContent` property, it would be more like this:

```
type Section {
  type Header {
    type H1 {
      title: String
      where textContent = title
    }
    type H2 {
      subtitle: String
      where textContent = title
    }
  },
  ...
}

```

Either way, wondering if you can do anything like that in Haskell, or another type-theory-oriented language like Coq.

In Haskell, a (binary) tree is represented as a recursive structure:

```
data Tree a = Nil | Node a (Tree a) (Tree a)

```

I don't know much Haskell, so I'm not sure how to represent the above HTML template "type" as a Haskell algebraic type (or if it is possible). But it seems like it could be defined as some form of an algebraic or a parameterized type.

My **first question** is, the kind of type the template can be called, and how to model it as a type (in Haskell, or Coq, or some language using a lot of type theory).

The **second question** is if an extended version of this template, which has looping, would be considered a dependent type (and then how to model it as a dependent type). That might look like this.

```
<template id="MyTemplateWithIteration">
  <section>
    <header>
      <h1>{title}</h1>
      <h2>{subtitle}</h2>
    </header>
    <ul>
    {each label in labels}
      <li>{label}</li>
    {/each}
    </ul>
    <footer>
      <cite>{author}</cite>
      <time>{year}</time>
    </footer>
  </section>
</template>

```

The reason I am thinking this could potentially be a *dependent* type is because dependent types deal with "forall", which seems like what the iteration is doing. Might be misunderstanding that part.

To finish up, what I normally just do is create a template *object*, instead of a type, and then from the template object you create an instance of some other type (the HTMLEntity in this case). But it seems like this could be formalized some more, and instead of a template object we could upgrade it to a template type, and then we would just be creating a template instance when instantiating it. Hoping to see how that definition would look for this highly nested structure.

Related note, wondering if this (modeling natural language trees using types) is similar. I'm not sure if they are modeling *tree* as a type, or just the nodes as types. Or perhaps grammars are nested types of some sort.

# Answer
You might be looking for CDuce programming language.
> 3 votes

# Answer
You might also be interested in the Ur/Web programming language.
> 2 votes

---
Tags: type-theory, functional-programming, dependent-types
---


title: How to calculate machine epsilon

text:
# Question
Title: How to calculate machine epsilon
In a binary system we know that the next floating point number after 4 is 4+1/32. What is the machine epsilon? Is it 1/32 and if yes, why?

# Answer
First note that $eps$ is not necessarily the same on every machine, it depends on architecture and precision. Also, the definition of $eps$ is not unique in literature. Often it is defined as the difference between $1$ and the next greater number that can be represented exactly, sometimes it is half of this difference (as it is the maximal relative error). In general, if you look at a machine number with base $b$, mantissa $m$ (and exponent $e$), you can define $$eps := \frac{b^{1-m}}{2}.$$

To your example: You would probably represent $4$ normalized as $(0.10000000)\_2 \cdot 2^3$. The next number $4+ \frac{1}{32}$ is then represented as $(0.10000001)\_2 \cdot 2^3$, i.e. you have $m = 8$ and thus $eps = 2^{-8}$.
> 2 votes

---
Tags: floating-point
---


# Question
Title: Dependent Type Theory Implementation of a Graph
In Haskell you find graphs defined like this:

```
data Graph a = GNode a (Graph a)

```

Or this:

```
data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)

class Graph g where
  type Vertex g
  empty   :: g
  vertex  :: Vertex g -> g
  overlay :: g -> g -> g
  connect :: g -> g -> g

```

Or this:

```
type Graph = Table [Vertex]
type Table a = Array Vertex a
type Bounds = (Vertex, Vertex)
type Edge = (Vertex, Vertex)
type Vertex = Int

```

I am wondering why it is not implemented more like this (this is JavaScript):

```
class Graph {
  constructor() {
    this.nodes = []
    this.edges = []
  }
}

```

Or perhaps in Haskell-ish:

```
data Graph = Graph
  { nodes :: [Node]
  , edges :: [Edge]
  }

```

For example, in this Graph in Coq, it looks more like the JavaScript version (though I don't understand the `Structure` in Coq):

```
Structure Graph := {
  V :> nat ; (* The number of vertices. So the vertices are numbers 0, 1, ..., V-1. *)
  E :> nat -> nat -> Prop ; (* The edge relation *)
  E_decidable : forall x y : nat, ({E x y} + {~ E x y}) ;
  E_irreflexive : all x : V, ~ E x x ;
  E_symmetric : all x : V, all y : V, (E x y -> E y x)
}.

```

Finally, here seems to be a complete Coq graph definition:

```
Inductive Graph : V_set -> A_set -> Set :=
  | G_empty : Graph V_empty A_empty
  | G_vertex :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x : Vertex),
      ~ v x -> Graph (V_union (V_single x) v) a
  | G_edge :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x y : Vertex),
      v x ->
      v y ->
      x <> y ->
      ~ a (A_ends x y) -> ~ a (A_ends y x) -> Graph v (A_union (E_set x y) a)
  | G_eq :
      forall (v v' : V_set) (a a' : A_set),
      v = v' -> a = a' -> Graph v a -> Graph v' a'.

```

My question is, what a proper definition of a graph is in Dependent Type Theory in formal type theory notation. Mathematically $G = (V, E)$, but in Coq and Haskell, things are a lot more functional/recursive. It seems weird that Haskell is defining it sometimes as a recursive structure. Wondering how to model this using the abstract type theory notation (using dependent types) and recursion if necessary, to get a better sense of realistic data structures in dependent type theory, and how to parse the formal notation. The types of graphs I am thinking about are directed, *cyclic*, and finite, non-hypergraphs.

# Answer
> 7 votes
So, there are two different things you are talking about.

1. The **definition** of a graph
2. The **encoding** of a graph

A Graph is always *defined* as a set of vertices and edges. This tells us what vertices are in the graph, and for any pair of vertices, whether there is an edge between them.

However, this definition is purely mathematical. A set isn't a "thing" that you can store in memory. So we need an *encoding* of a graph, so that the abstract mathematical set operations can be mapped onto concrete algorithmic operations.

Once you're talking about encoding, there are many different ways to implement a graph, all of which will give you something that is (in a sense) equivalent to the mathematical definition. But, there are practical trade-offs with different encodings:

* What operations are fast?
* What operations are easy to implement?
* How much memory does the graph take?
* How easy is it to use the graph in different settings.

In JavaScript, all types are dynamic, so it's easy to just say "A graph is a list of nodes and a list of edges", because the language doesn't ever require that you formally specify what a node or an edge looks like. It doesn't care, and if you make a mistake, it will just crash at runtime.

Notice that your JavaScript version of a graph doesn't actually specify how nodes and edges are represented. What does an edge look like? If you insert an edge as a 2-element array, but try to access it as an object, you will have a runtime error.

Haskell and Coq's definitions try to solve this issue with *type safety*. They have a formal definition of the different forms a Graph can take, so that you always know at compile-time which operations on it are valid or not.

Let's look at the versions and their tradeoffs:

```
data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a)

```

This version is interesting, because it is an *inductive* definition of a graph, that allows you to implement graph operations easily as recursive functions. So you know that a graph is always empty, a single vertex, the overlay of two graphs, or the connection of two graphs, and you can safely pattern match on these 4 cases.

```
class Graph g where
  type Vertex g
  empty   :: g
  vertex  :: Vertex g -> g
  overlay :: g -> g -> g
  connect :: g -> g -> g

```

This isn't actually an implementation of a graph, but instead is an *interface* for a graph. It says what operations are available on a graph, but not how they're implemented. Users could provide their own `Graph` instances, and can write code that is generic over which `Graph` implementation is used. This helps bring back some of the flexibility that we had in JavaScript but lost when adding types.

```
type Graph = Table [Vertex]
type Table a = Array Vertex a

```

This is a classic "Adjacency List" implementation of a graph: we store the outgoing edges for each vertex. It is space efficient, and allows for quick BFS and DFS, but is slower for checking the existence of an edge, or deleting an edge.

```
Structure Graph := {
  V :> nat ; (* The number of vertices. So the vertices are numbers 0, 1, ..., V-1. *)
  E :> nat -> nat -> Prop ; (* The edge relation *)
  E_decidable : forall x y : nat, ({E x y} + {~ E x y}) ;
  E_irreflexive : all x : V, ~ E x x ;
  E_symmetric : all x : V, all y : V, (E x y -> E y x)
}.

```

This is an interesting representation. First, it's similar to a typeclass, in that it's abstract: it works for any types $V$ and $E$ so long as they can be coerced into numbers and edge-lookup functions. This isn't saying "this is how you can represent a graph", it's saying "here's an interface for graph representations".

Second, because we are in a dependently typed setting, we want to encode some properties of the graph, so that we can't create ill-formed graphs. We can then use these properties when proving things about graphs later on. Here, there are three properties that we require all graphs to have:

1. The encoding must be irreflexive i.e. there are no self edges
2. The encoding must be symmetric i.e. any time there's an edge u-\>v, there's also an edge v-\>u
3. The edge relation is decidable i.e. we can take

The third condition is important because Coq is a total language. It doesn't allow for any non-terminating code, so we need to prove that our edge lookup actually halts.

Finally, there's the Coq graph definition:

```
Inductive Graph : V_set -> A_set -> Set :=
  | G_empty : Graph V_empty A_empty
  | G_vertex :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x : Vertex),
      ~ v x -> Graph (V_union (V_single x) v) a
  | G_edge :
      forall (v : V_set) (a : A_set) (d : Graph v a) (x y : Vertex),
      v x ->
      v y ->
      x <> y ->
      ~ a (A_ends x y) -> ~ a (A_ends y x) -> Graph v (A_union (E_set x y) a)
  | G_eq :
      forall (v v' : V_set) (a a' : A_set),
      v = v' -> a = a' -> Graph v a -> Graph v' a'.

```

This version provides a concrete implementation, that (I think) fulfills the interface you gave. In particular, it says we can build a graph in 4 ways:

1. A graph can be empty
2. We can add a vertex to a graph
3. We can add an edge to a graph
4. We can map an equality over a graph

The beauty of this implementation is that the vertex and edge sets are stored *at the type level*. This is the magic of dependent types: the type of the graph depends on the values it contains. So, when adding an edge, the type system ensures that we can't possibly add an edge between two vertices that aren't in our vertex sets.

Secondly, this implementation is inductive, similar to the Haskell one, so writing proofs about this graph by induction will be easy.

---
Tags: graphs, type-theory, dependent-types
---


# Question
Title: Largest weight-limited connected subgraph: NP-complete?
When playing Terra Mystica, it might be useful to predict how many spades you will get throughout the game, and use this information to decide where to build, such that you stand a good chance of having the longest network. Let's abstract that into the following problem:

* Let a graph $G$ be given, $G = (V, E)$.
* Associate a terraforming cost with each vertex, $C : V \mapsto \\{0, 1, 2, 3\\}$.
* You're given some number of spades, $s$.

Your goal is to find a set of vertices $V^\*$ such that:

* You can afford to build on all of them, $\Sigma\_{v \in V^\*} C(v) \leq s$
* They're all next to each other: the graph $(V^\*, V^\* \times V^\* \cap E)$ is connected.
* It is the largest such set: for all $V'$ which satisfy the previous conditions, $|V^\*| \geq |V'|$.

The decision version takes a threshold parameter $k$ and asks "is there a vertex set $T$ with size $|T| \geq k$ and which satisfies the first two criteria?"

What is the complexity of this problem? By eyeball, it's obviously in NP; is it NP-complete? Is it well-studied under some name unknown to me?

# Answer
> 3 votes
The decision version is NP-complete so the problem is NP-hard. The following is a reduction from 3SAT.

For an instance of 3SAT with $n$ variables $x\_1,\ldots, x\_n$ and $m$ clauses, create a graph as follows:

1. For each variable $x\_i$ create two vertices $v\_i^0, v\_i^1$ with cost $1$. Create an edge between each two vertices of these $2n$ vertices, i.e. the $2n$ vertices induce a clique.
2. For each variable $x\_i$ create a vertex $v\_i$ with cost $0$, and two edges $(v\_i, v\_i^0)$ and $(v\_i,v\_i^1)$.
3. For each clause $c\_l$ with variables $x\_i,x\_j,x\_k$, create a vertex $u\_l$ with cost $0$, and three edges $(u\_l, v\_i^{b\_i})$ (if the literal is positive, $b\_i=1$, otherwise $b\_i=0$, and the same below), $(u\_l, v\_j^{b\_j})$ and $(u\_l, v\_k^{b\_k})$.

Then we ask if there is a connected vertex set $T$ with size at least $2n+m$ and the sum of cost is no more than $n$.

Now if the instance of 3SAT has a feasible solution where $x\_i=b\_i$, we can make $T$ consist of all $v\_i$s, $u\_l$s and $v\_i^{b\_i}$s.

On the other hand, if $T$ exists, because you can afford at most $n$, at most $n$ vertices among $v\_i^0, v\_i^1$s are chosen, thus all $n+m$ vertices with cost $0$ must be chosen. This means:

1. Since $v\_i$ is chosen, at least one vertex of $v\_i^0$ and $v\_i^1$ is chosen. Because at most $n$ vertices among $v\_i^0, v\_i^1$s are chosen, exactly one of $v\_i^0$ and $v\_i^1$ is chosen. We assign $x\_i$ accordingly.
2. Since $u\_l$ is chosen, at least one corresponding literal has value $1$, thus the clause is satisfied.

So the instance of 3SAT has a feasible solution.

# Answer
> 1 votes
The decision version of the Terra Mystica Network problem is NP-hard.

Hee's a reduction from $k$-MST with edge weights in $\\{1, 2, 3\\}$, see https://en.wikipedia.org/wiki/K-minimum\_spanning\_tree.

Let's recap the decision version: you're given a graph $G = (V, E)$, an edge cost function $W: E \mapsto \\{1, 2, 3\\}$, a target size $t$ and a cost limit $c$. An instance is a yes-instance if there exists a $t$-vertex tree with total edge lost at most $c$.

To turn this into an instance of the Terra Mystica network decision problem, add a vertex $v\_e$ on the middle of each edge $e$; replace $e = \\{v, w\\}$ with two edges $\\{v, v\_e\\}$ and $\\{w, v\_e\\}$. Let $C(v\_e) = W(e)$, and let $C(v) = 0$ for all $v \in V$. Also attach a path of length $|E|$ and total cost $0$ to each vertex in $V$. Let $k = t(|E|+1) + (t - 1)$ and let $s = c$.

If we can find a $k$-MST, we can easily turn it into a Terra Mystica network: simply use $v\_e$ in the network for all edges $e$ used in the tree, carry over the vertices and flood-fill into the attached paths. This obeys the cost constraint because they're equal and the flood-filled vertices are free. Each vertex turned into $|E|+1$ vertices, all of which are in the solution, as are $t-1$ edges, so the total solution size is $t \cdot \left(|E|+1\right) + (t-1)$, exactly what's required. Trees are connected, so the Terra Mystica network is as well.

On the other hand, let a (connected) Terra Mystica network be given of size at least $t \cdot \left(|E|+1\right) + (t-1)$ and cost at most $s = c$. If it includes at most $t - 1$ of the vertices carried over from the $k$-MST instance, and at most all the $v\_e$s, then its total size is at most $$(t-1)(|E|+1) + |E| = t|E| - |E| + t - 1 + |E| = t|E| + t - 1 = t \cdot (|E|+1) - 1 \< t \cdot (|E|+1) + (t-1)$$

This is because each of the length-$|E|$ paths is only accessible through the vertices carried over from $V$. But this is impossible, as we assumed the solution size is at least $t \cdot (|E|+1) + (t-1)$.

If it has *more* than $t$ of the vertices from $V$, we can drop some of them while keeping the solution connected: $t$ vertices plus $t$ paths of length $|E|$ plus $(t-1)$ of the $v\_e$ vertices to connect them also form a solution; we may need to flood-fill into partially included attached paths. If the solution includes more than $t-1$ of the $v\_e$ vertices, we can eliminate some by computing any (e.g. a minimum-weight) spanning tree only on the vertices and edges in the solution (treating the $v\_e$ vertices as edges). The solution includes *at least* $t-1$ of the $v\_e$ vertices, else it wouldn't be connected.

Then the vertices from $V$ and the edges corresponding to the $v\_e$ vertices form a $t$-vertex tree in $G$ with cost at most $c$. So if we have a solution to the Terra Mystica network problem, we also have a solution to the $k$-MST problem.

QED.

**Commentary**

Terra Mystica is played on the faces of a hexagon tessellation of the plane—or rather, a finite subset of such hexes. The $k$-MST problem is NP-hard for *planar* graphs with edge weights in $\\{1, 2, 3\\}$. The reduction preserves planarity. Hence, with this reduction we can (hopefully) abstract away fewer parts of Terra Mystica than with xskxzr's reduction from 3SAT, and still have a hardness result.

One step is missing: we need to be able to embed a planar graph on a hex face grid. My 15 second literature search came up empty handed, which is probably mostly to blame on its duration.

One might hope that if we can draw it this way, we can fill the "empty space" with (enough) prohibitively expensive vertices and have something that vaguely resembles a Terra Mystica board. Maybe we can even put in a river somewhere and not have the reduction fall apart.

**More commentary**

I reduced one constrained optimization problem to another. The decision version of a constrained *optimization* problem (one of maximizing $f(x)$ subject to $g(x) \>= t$) becomes a constraint *satisfaction* problem, one of finding an $x$ such that $f(x) \>= t\_1$ and $g(x) \>= t\_2$. Hence, when looking for reduction candidates you don't have to be concerned about "oh well this one constrains on x and optimizes for y but the other problem is the other way around"—when you work with the decision versions it all becomes the same thing. It's all just constraints.

---
Tags: complexity-theory, graphs, optimization, np-complete, np-hard
---


# Question
Title: How does cache partitioning prevent covert/side-channel attacks?
In a report on an open-source separation kernel (Muen kernel) I was reading, in the future work section, it says that cache coloring can be implemented to prevent covert/side-channel attacks.

It is mentioned that

> In a second step each subject is associated with a color. All subjects of a given color share the same cache partition. In turn subjects of differing color have no access to identical cache locations, which means the cache cannot be used as a side-channel.

I understand what page coloring/cache partitioning is, but I do not understand how having different subjects use different cache partitions can solve side-channel attacks. Can anyone enlighten me on this?

# Answer
> 4 votes
Most **L2** (and L3) caches are indexed with the physical (not virtual) address modulo a power of two that is larger than the page size. This allows different physical address colors to map to different indices, isolating replacement decisions (i.e., only accesses from the same color can cause a cache miss). The added latency from cache misses (often measured in the attacker program) can reveal the index of cache line that was replaced.

Partitioning also avoids *capacity* use measurement, which provides less specific information (compared to used index).

Color-based partitioning would typically not avoid *bandwidth* use measurement in a shared cache under default hardware configurations (which tend to be demand-based rather than fair-share; strict fair-share decreases throughput under variable demand).

For **L1** caches, isolation based on physical page color would have no effect in caches that are virtually indexed. L1 sharing is more easily restricted to a temporal granularity that would not leak a significant amount of information.

It might be noted that *performance* isolation for multi-use systems (where different uses may give different values to different resources and even to the predictability of resource availability) is the primary/original motivation for Intel's Cache Allocation Technology ("ensuring consistent performance and prioritizing important interactive applications"), but such features can help narrow side-channels for security-oriented isolation.

---
Tags: memory-management, cpu-cache, memory-hardware, memory-access, caching
---


# Question
Title: Big-O / $\tilde{O}$ -notation with multiple variables when function is decreasing in one of its arguments
Say we have an algorithm that takes an input a triple ($X$, $A$, $\epsilon$), where $X$ is a sequence of $n$ bytes, of which the algorithm might query only a subset, and $A$ and $\epsilon$ are numbers with $A \geq 1$ and $\epsilon \> 0$. It is claimed that this algorithm runs in time

$$ \tilde{O}(\frac{n}{A^3 \epsilon}) $$

as $n \to \infty$, $A \to \infty$ and $\epsilon \to 0$.

(Note that $\tilde{O}$ means big-O except ignoring logarithmic factors. For functions of one variable, $f(n) \in \tilde{O}(g(n))$ iff there exists a $k \geq 1$ such that $f(n) \in O(g(n) \cdot \log^k g(n)$.)

**My question is, what exactly does this mean formally?**

So this is another question about "asymptotic notation with multiple variables". There are existing questions about this, but they don't apply to this case.

This case is different because the expression $\frac{n}{A^3 \epsilon}$ is decreasing in one of its arguments, namely $A$. The standard definition for asymptotic notation with multiple variables given in Wikipedia breaks down in this case, as described below.

I also tried some "obvious" alternative definitions, which also seem fail, as described below.

(The actual algorithm that I'm wondering about is Algorithm IV in this paper. It's an approximation algorithm that outputs an estimate of $f(X)$ for a certain function $f$, and is claimed to "run in time $\tilde{O}(\frac{n}{A^3 \epsilon})$". From context one can infer that this asymptotic claim is supposed to be true as $n \to \infty$, $A \to \infty$, and $\epsilon \to 0$. (Instead of, say, when $n \to \infty$, $A \to \infty$ and $\epsilon \to \infty$). $A$ and $\epsilon$ determine the error bounds. The larger $A$ and $\epsilon$ are, the looser the bounds are, and the farther the output is allowed to diverge from $f(X)$.)

So, let $F(n,A,\epsilon)$ be the number of operations performed by the algorithm when run with an input of size $n$ and parameters $A$ and $\epsilon$. (If different inputs of size $n$ perform different numbers of operations, let $F(n, A, \epsilon)$ be the maximum.) The claim, whose formal meaning is still unclear, is now

$$F(n, A, \epsilon) \in \tilde{O}(\frac{n}{A^3 \epsilon}).$$

If we unpack the $\tilde{O}$-notation, the unclear claim is that there exists some $k \geq 1$ such that

$$F(n, A, \epsilon) \in O(\frac{n}{A^3 \epsilon} \log^k \frac{n}{A^3 \epsilon}).$$

### Failure of the standard / Wikipedia definition

Take this definition and adapt it in an obvious way for the situation where one of the variables approaches $0$ instead of $\infty$, and where we are using $\tilde{O}$ instead of $O$. We get this:

> There exist $C \> 0$, $M$, and $k \geq 1$ such that if at least one of $n \geq M$, $A \geq M$ and $\frac{1}{\epsilon} \geq M$ holds, then $$| F(n, A, \epsilon) | \leq C | \frac{n}{A^3 \epsilon} \log^k \frac{n}{A^3 \epsilon} |.$$

This fails because we can choose $(n, A, \epsilon)$ so as to make $A$ arbitrarily large while the right-hand side remains constant. That is, for an arbitrarily large $N$, set $n = N^3$, $A = N$, and $\epsilon = \frac{1}{7}$. Regardless of $N$, the right-hand side is $C |7 \log^k 7|$.

But as $N \to \infty$, $F(N^3, N, \frac{1}{7})$ must grow without bound (not necessarily monotonically). This is because, for example, it takes the algorithm $O(\log N)$ operations just to read the bits of the binary representation of the second argument. So for large enough $N$, the left-hand side is larger than the right-hand side, violating the inequality. So the claim doesn't hold.

Adapting the definition from this answer , we would get this claim:

> There exist $C \> 0$, $n\_0, A\_0, \epsilon\_0$ and $k \geq 1$ such that if all of $n \geq n\_0$, $A \geq A\_0$ and $0 \< \epsilon \leq \epsilon\_0$ hold, then $$| F(n, A, \epsilon) | \leq C | \frac{n}{A^3 \epsilon} \log^k \frac{n}{A^3 \epsilon} |.$$

This doesn't work for the same reason as the previous claim. We can make $A$ arbitrarily large while keeping the right-hand side constant.

---

I have seen the article "On Asymptotic Notation with Multiple Variables". It doesn't seem relevant, because it doesn't deal with the case where the function inside the asymptotic notation is decreasing in one of its arguments.

It makes sense that, when dealing with approximation algorithms, it would be useful to make claims like "this algorithm runs in time $\tilde{O}({\frac{n}{A^3 \epsilon}}$)". In particular, it **seems there should already be a standard definition in the field of approximation algorithms** for $O$/$\tilde{O}$ notation with multiple variables when the function is decreasing in one of its arguments. But I could not find such a definition. I looked at several articles about classifying the asymptotic complexity of approximation algorithms, but did not find anything that seemed relevant. In particular, the concepts of "polynomial-time approximation scheme" and "fully polynomial-time approximation scheme" seem to be irrelevant here.

---

### Appendix: attempted alternative definitions

I thought this definition might work:

> Let $f\_A(n)$ be an increasing function and $f\_\epsilon(n)$ be a decreasing function such that $f\_A(n) \to \infty$ and $f\_\epsilon(n) \to 0$ as $n \to \infty$. The following holds: $$(n \mapsto F(n, f\_A(n), f\_\epsilon(n))) \in \tilde{O}((n \mapsto \frac{n}{f\_A(n)^3 f\_\epsilon(n)} )). $$

(So this is a claim about the asymptotic behavior of a function of one argument.)

But it also fails. You can define $f\_A$ and $f\_\epsilon$ so that $\frac{n}{f\_A(n)^3 f\_\epsilon(n)}$ remains constant as $n \to \infty$; meanwhile $F(n, f\_A(n), f\_\epsilon(n))$ must grow without bound, even if slowly and non-monotonically, as $n \to \infty$, making the claim false.

You could add the requirement that $f\_A$ and $f\_\epsilon$ be chosen so that $\frac{n}{f\_A(n)^3 f\_\epsilon(n)} \to \infty$ as $n \to \infty$. That doesn't help. $f\_A$ and $f\_\epsilon$ can be chosen so that $\frac{n}{f\_A(n)^3 f\_\epsilon(n)}$ grows very slowly compared to $f\_A(n)$, causing $F(n, f\_A(n), f\_\epsilon(n))$ to grow faster than $\frac{n}{f\_A(n)^3 f\_\epsilon(n)}$.

(I'm now thinking that maybe one should add some requirement that $f\_A$ and $f\_\epsilon$ be chosen so that $\frac{n}{f\_A(n)^3 f\_\epsilon(n)}$ grows "sufficiently fast". But this seems like it would be rather elaborate.)

# Answer
> 2 votes
The tilde usually suppresses logarithmic factors. So in your case, the true upper bound should be something like $$ O\left(\frac{n}{A^3 \epsilon} \bigl(\log n \log A \log \frac{1}{\epsilon}\bigr)^{O(1)} \right). $$ (Equivalently, you can replace $\log n \log A \log \frac{1}{\epsilon}$ with $\log n + \log A + \log \frac{1}{\epsilon}$, or equivalently, with $\log \frac{nA}{\epsilon}$.)

You're right that $\tilde{O}$ notation is ambiguous, but in most cases the intended meaning is apparent.

---
Tags: complexity-theory, asymptotics, approximation
---


# Question
Title: How to get the upper, lower and average bound of a given algorithm?
How to get upper, lower, average bound of given algorithm? What should be the first step I should do? I search on the internet and only give me the definition of those 3. For example if take the algorithm of nlog(n)+2 then how do we find the lower and upper bound of this? What would be the first step?

# Answer
> 0 votes
When we talk of best case, worst case, and average case, it is in the context of algorithms whose running time depends on the input and not just on its length. If the algorithm always runs in time $n\log n + 2$, then the best case, worst case, and average case are all the same.

For a non-trivial example, consider quicksort. Quicksort always runs in time $O(n^2)$, and there is a sequence of arrays, one of each length, on which quicksort runs in time $\Theta(n^2)$. Therefore the worst case running time of quicksort is $\Theta(n^2)$. The best case running time varies according to the implementation – it can be $\Theta(n\log n)$ or $\Theta(n)$.

What about average case? Whenever we talk about average case, we need to introduce a distribution, according to which the average is taken. For sorting, the standard distribution is a random permutation of $1,\ldots,n$. The average case running time of quicksort, with respect to this distribution, is $\Theta(n\log n)$.

In other words, even though there are some arrays which are "difficult" or "bad" for quicksort, causing it to have quadratic running time, on "most" arrays it behaves much better, having a linearithmic running time. The running time depends not only on the length of the input array, but also on its order. This causes the discrepancy between worst case and average case for quicksort, and for many other (though not all) sorting algorithms.

---
Tags: algorithms, data-structures, asymptotics
---


title: Rational versus intelligent agents

text:
# Question
Title: Rational versus intelligent agents
Question about "Artificial Intelligence: A Modern Approach by Russell and Norvig"

I have issue to distinguish clearly between intelligent and rational agent presented by Norvig and Russel. What I understand is that rational agent think and act like human but not intelligent agent. Thus, Russel present 4 types of intelligents agents – Simple reflex agents – Model-based reflex agents – Goal-based agents – Utility-based agents

My question is : could Goal-based agents be a rational agents at the same time ? Does this concept limite intelligence to just human intelligence ? Some paper do not make distinction between these two terms.

# Answer
Before I go straight to your question, we have to get a clear picture of these two terms that might seem confusing;

1.rationality(an agent is able to perform given task x after analysing y,that is right fit for x).

2.intelligence.(an agent is able to perform given task x after analysing y inline with reasoning ie..why x?....).

could Goal-based agents be a rational agents at the same time ? Basing on the above two hints,the answer is yes.

Does this concept limit intelligence to just human intelligence ? According to artificial intelligence research,so far,we haven't reached at the level of human intelligence (artificial general intelligence).

Hope this can give you some insights.
> 1 votes

---
Tags: artificial-intelligence
---


# Question
Title: How does RAMDAC get notified about framebuffer write?
I'm learning computer graphics, and I read this course lecture in order to understand how graphics I/O works under the hood. But the following explanation was not very clear to me:

> The values in the framebuffer are converted from a digital (1s and 0s representation, the bits) to an analog signal that goes out to the monitor. A video card’s RAMDAC performs this operation, once per frame. This is done automatically (not controlled by your code), and the conversion can be done while writing to the framebuffer.

How does `RAMDAC` get notified about the framebuffer write? Is there an IOCTL required from OS? or there is a circuitry somewhere that maps the write to `RAMDAC` input?

# Answer
> 2 votes
It probably depends on the architecture in general, but bear in mind that the phrase "the conversion can be done while writing to the framebuffer" is quite vague. The important point is that generating the video signal is a hard real-time operation, and the graphics hardware is designed to ensure that it always happens, even if someone is trying to write to the framebuffer at the same time.

There are a few ways this could be achieved. Some possibilities include:

* Reads and writes to the framebuffer might always happen at different times. If you consider a square wave clock, for example, writes could happen on the leading edge of the clock signal and reads could happen on the trailing edge. This way, the result of the write is always available when the read occurs.
* If there is contention between a read and a write, the write could stall or be buffered somewhere.
* Reads from the framebuffer to generate the video signal could be buffered in a FIFO or something like that. If a write occurs, it could be allowed to happen as long as the FIFO hasn't drained.

It's possible that there could (as you say) be some kind of bypass circuitry, similar to forwarding logic in CPUs. The input to the RAMDAC could be a multiplexer, with one input directly from framebuffer RAM and another from somewhere else.

I think this is unlikely, because it seems excessive to implement extra circuitry just to ensure that a write that is happening right now appears on this frame. A buffer or stall seems much more likely.

# Answer
> 2 votes
The "once per frame" part is totally wrong.

Traditionally, a "RAMDAC" combines a little bit of RAM and three Digital to Analog Converters, for three colours. The RAM part is used for indexed colours mode, for example in the old VGA 320x200x256c mode, each colour is indexed from a table, sometimes named "palette". For "truecolor" modes, 16 or 24bits, the RAM part is bypassed and pixel colours are directly stored in the framebuffer.

To generate a picture, the framebuffer is continuously read and data (=pixels) are forwarded to the DACs. Imagine a counter which is reset after every frame (typ. 60-80Hz refresh), then incremented for every pixel. With modern high resolution displays, pixel read rate can exceed 200MHz (a different pixel is transmitted on the wire between the computer and the screen every 5 nanosecond, or less).

Nowadays RAMDACs are integrated in the GPU for the VGA output. For digital outputs, HDMI, DisplayPort, there is no analog "DAC", except in the LCD panel itself.

For an example of traditional RAMDACs, when it was a separate chip, look for "Bt485A"

---
Tags: computer-architecture, graphics, memory-access, video
---


# Question
Title: The well-known classifiers that can be trained/tested in linear time
I am interested in collecting the list of the classifiers that (depending on their setting) **can have** linear time complexity (both in training and testing step) with respect to the number of samples $n$, the number of features of each sample $m$, and the number of classes $c$.

In other words, I am seeking for a list of the well-known classifiers that can have the complexity of **$\mathcal{O}(mnc)$** or lower.

1- I know that Naive Bayes classifiers are so; given that the parameters of the utilized probability distributions can be estimated in linear time (e.g. Poisson Naive Bayes and Multinomial Naive Bayes)

2- I also know that when K-NN is utilized as classifier (counting the K-nearest neighbors and choosing the most-voted class), it is also included in this list.

Although this list, in theory, can be extended infinitively, I am interested in completing the list by the well-known classifiers by the CS community.

I searched the web, a lot, but seemingly, there is no page even speaking about such subject or such list. The only thing that I found was a lot of info about "linear classifiers" whose scope is much more general than my question (even their list includes SVM and etc.).

# Answer
> 0 votes
# Time Complexity of Training and Testing

## Linear with respect to training samples ($n$) and samples features ($m$) and number of classes ($c$).

Letting the list provided in the weblog of @Martin\_Thoma as the basis, I exhaustively searched the web and reached the following list.

The following classifiers potentially have computational complexities less than or equal with $\mathcal{O}(mnc)$ complexity) in both of the training and testing phases.

The following classifiers are nonlinear either in the training or in the testing phase:

# Answer
> 1 votes
You might want to read my blog post Comparing Classifiers, especially the MNIST summary.

# Time Complexity of Training

## By Training Samples

Let $n$ be the number of training samples.

The following classifiers can perform at least on training / fitting step in $\mathcal{O}(n)$:

* Neural Networks: You can take a fixed batch size. Then increasing $n$ is simply having more mini-batches to train on.
* $k$-nearest-neighbors: All "training steps"

The following classifiers cannot perform at least one training / fitting step in $\mathcal{O}(n)$:

* ???

I am unsure about the following:

* SVMs
* Decision Trees: I'm relatively sure it is linear, but I would need to go through one of the training algorithms

## By classes

If $n$ is the number of classes, then the training of $k$-NN is in $\mathcal{O}(1)$. If you keep the number of samples and k constant, then it doesn't matter if you have 2 classes or $10^{100}$.

I'm unsure about:

* Neural Networks: The size of the last layer grows. My intuition is that this is in $\mathcal{O}(n)$, but I need to put more thought into it. I am, however, not sure if the Big-O Time Complexity makes a lot of sense for this classifier. If you look at the tables in Appendix D, you see that in real problems the FLOPs are dominant in the beginning. Given a problem, you usually you can't influence the number of classes. And the wall-clock time complexity of training for two classes is vastly different for different classifiers. So much, that up to a reasonable amount of classes you will likely not see the asymptotic behavior.
* Decision trees might even be in $\mathcal{O}(1)$. I have to give impurity measures a closer thought.

---
Tags: complexity-theory, time-complexity, machine-learning, classification, pattern-recognition
---


title: What are known 3SAT to 2SAT reductions?

text:
# Question
Title: What are known 3SAT to 2SAT reductions?
Is there a way to convert a 3SAT formula into a equisatisfiable 2SAT formula? Each method is of interest, even those that grow exponentially. (So if, for example, my 3SAT formula has 16 variables and 32 clauses, a transformed 2SAT formula would have 2ˆ16 variables and / or 2ˆ32 clauses)

An example of a 3SAT formula I would like to convert is:

A xor B xor C

Or the same in CNF:

(A or B or C) and (A or !B or !C) and (!A or !B or C) and (!A or B or !C)

# Answer
> 2 votes
You seem to be asking about logically equivalent 2CNF functions rather than equisatisfiable ones. Not all Boolean formulae can be expressed as 2CNF formulae. Your example $(a \oplus b \oplus c)$ is one example of such a formula. $(a \lor b \lor c)$ is another. These formulae are simply not expressible equivalently in 2CNF, even with an exponential increase in formula size.

# Answer
> 3 votes
Yes, there is. Test whether the 3SAT formula is satisfiable or not. If it is, convert it to the formula True. If it is not, convert it to the formula False. This can be done in exponential time, e.g., by trying all possible assignments, or by your favorite method for testing satisfiability of a 3SAT formula.

Under the strong exponential-time hypothesis, this is optimal: there is nothing faster.

In particular, any procedure for converting into an equisatisfiable 2SAT formula can be used to test satisfiability of 3SAT: first convert into an equisatisfiable 2SAT formula, then test the satisfiability of the corresponding 2SAT formula (can be done in linear time. This gives a method for testing the satisfiability of a 3SAT formula, whose running time is essentially the same as the running time of the conversion procedure. Now the strong exponential-time hypothesis says that any method for testing satisfiability of 3SAT formulas requires exponential time. It follows that any method for conversion also requires exponential time.

---
Tags: algorithms, complexity-theory, reductions, satisfiability, 3-sat
---


title: Optimal meeting point

text:
# Question
Title: Optimal meeting point
I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point and to minimize the time/distance for everyone.

I'm looking for information on that problem, but I've only been able to find advanced paper on this problem.

**My questions:**

* Is it part of a more general problem?
* Is graphs the best way to implement it? (the nodes are the possible meeting points, the edges are the possible roads for example..) How do current programs work, for example using maps like Google Map?
* Is it P or NP?

**My difficulties to understand the problem and to find more informations about it**

I know it's a bit vague, but I've got some difficulties because I don't know much about this kind of problems. I was just wondering one day "how to find the best restaurant in terms of distance to meet with some friends". I don't know what is mathematically the parameter that I should minimize to be "fair" (the sum of the distances of the $n$ individuals to the meeting point? The average?...).

**Response to comment:** (assuming that using graph is the best way to do it)

In input, we have a graph and we have the $n$ individuals (a list of $n$ vertices if we implement it with graphs, even if it means to add them to the graph), and in output, we get the optimal meeting point (i.e. the vertex which is at the minimal distance from all the $n$ individuals).

# Answer
There are two kinds of minimizing in this sense,

* the first is to minimize the **sum** of the distances.
* the second is to minimize the **maximum** distance (finding a restaurant where the farthest friend is as near as possible).

In both cases it's not NP-Hard, since you can calculate all-pairs shortest path in $O\left(N^2\log\left( E+N \right)\right)$, sum up the distances from each restaurants to all friends and compare the sums.

**Ps** A special case is points laying on a line segment. The solution to the first type will be the restaurant dividing the vertices in two most-possible equal groups (has so many friends on its left as many friends on its right), the reason this works can be derived from the fact that median minimize absolute deviation. The solution to the second problem is trivially the nearest restaurant to the middle point between the two farthest friends.

**Ps2** In trees you can solve the second type using two DFSes to find the two farthest points and then choose the point in between them minimizing the distance to both of them.
The second type however, can be done in trees using a bfs traversal from leaves, counting the number of friends and distance to them in subtree of each node. Then a second bfs from the root of the tree summing all the numbers up.
> 4 votes

# Answer
narek gives the polynomial-time algorithm. The more general problem is the facility location problem. This includes several problems but the basic idea is that you want to know where to build your restaurants (plural) to minimize the distance people need to travel (with multiple restaurants, we just assume that people want to eat *somewhere*, not that they all want to eat together) or to compute how many restaurants you need so that everybody is within some distance of one.

As for what metric to optimize, note that minimizing the sum is the same thing as minimizing the average, which is just the sum divided by $n$. The main alternative is to minimize the maximum distance anyone needs to travel. These can have rather different effects. Suppose you have 99 people in Los Angeles and one in New York. If you minimize the average distance, the one guy in New York flies to LA; if you minimize the maximum distance, everybody schleps over to somewhere like Omaha.

It's not my area of research but I've been to plenty of seminars on it, which suggests that it's an active field with plenty of open problems. There should be plenty for you to do, at whatever level you want to work at.
> 3 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: What algorithm should I use to find a minimal tree that include certain nodes within a graph?
Assume we need to include a certain set of nodes in the tree within the whole graph, the generated tree can contain nodes other than the specified set of nodes. We also need the number of edges (or the total amount of edge weight) included in the tree is minimum.

# Answer
This is the famous Steiner tree problem in graphs, which is known as NP-hard.
> 10 votes

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


# Question
Title: Calculating the probability of data loss of a RAID 1+0 system
I have a task where a RAID 1+0 system (A RAID 0 connects two RAID 1's with two disks each = makes 4 disks in total) is given with no further details. Then let p be the probability that one disk shows signs of failure. The variable p is not further defined.

Now I've received the task to calculate the probability that there will be a data loss in this RAID 1+0 system and I have literally no idea how solve this. I know that RAID 1+0 systems can cope with failure of the 1st and 3rd disk without having any data loss.

Please enlighten me, thanks!

# Answer
A RAID 1 system with two disks fails if both disks fails. If each disk fails with probability $p$, then this happens with probability $p^2$.

The RAID 1+0 system fails if any of the two RAID 1 component systems fails. Since each of them fails with probability $p^2$, the probability that either fails is $2p^2 - p^4$ (using inclusion-exclusion).

In symbols, let $x\_1,x\_2,x\_3,x\_4$ be the failure status of the disks, that is, $x\_i$ is true if the $i$th disk failed. The entire system fails if $$ (x\_1 \land x\_2) \lor (x\_3 \land x\_4). $$ The variables $x\_1,x\_2,x\_3,x\_4$ are independent $\mathrm{Bernoulli}(p)$ random variables. A short calculation (given above) shows that $$ \Pr\[(x\_1 \land x\_2) \lor (x\_3 \land x\_4)\] = 2p^2 - p^4. $$

You can solve all similar questions in the same way.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: How can a stack-based VM be Turing-Complete?
I was trying to implement a stack-based Virtual Machine (e.g. like JVM or some early version of Lua) for some benchmarks in order to test its performance against a Register-based VM.

I originally implemented it as having a global stack for all values and an array of instructions, where for the sake of simplicity, no functions are implemented, but only goto statements that jump occationally in between the array of instructions, in order to operate on the stack. All instructions are decoded in a linear fashion, and then loaded into an array, which in turn gets fed into the gigantic switch, looping itself while directing instructions to different operations. The values contained in the instructions are decoded seperately within the switch, and then get stored into the global stack, when needed.

Later on, I heard that in order to be Turing-equivalent, the stack machine must have at least two stacks. So the question I'm asking here, is 1) is my original design Turing-equivalent? 2) If not, how to revise the design so that it would be Turing-equivalent?

The reason for the stack VM to be Turing equivalent is that then its speed and efficiency can be compared to another Turing-equivalent custom-made Register machine. Please correct me on this if it does not :)

Thanks!

# Answer
You are confusing stack-oriented programming languages (resp. their interpretation model) with pushdown automata. The former can be Turing-complete because they *can* access an (infinite) random-access memory; the latter does not have any memory but the (one) stack.

The description of your machine (model) is not very clear. I think you can decide its power on your own given the above criterion.
> 4 votes

# Answer
If the stack machine is only allowed to access the top of the stack, and apart from the stack it only has a finite amount of storage, then it's a pushdown automaton. Pushdown automata are not Turing-complete; non-deterministic pushdown automata can only recognize context-free languages, and deterministic ones even less.

With two stacks, such that the machine can push and pop from either stack, the machine is equivalent to a Turing machine. This is fairly easy to see: given a Turing machine, you can build an equivalent two-stack automaton by pushing the input onto one stack, and then treating forward motion on the tape as popping from the first stack and pushing onto the second stack, and vice versa for backward motion.

If the stack machine is allowed to access data from any point in the stack, which is normally the case when a stack machine is used to build a virtual machine, it's a different story. In this case the shape of the stack doesn't matter, what you have is a random-access machine. From the point of view of computability, it's the same thing as a register machine, it's just a matter of how you name the registers: by calling it “stack machine”, you're just saying that the registers are numbered in a certain way.

RAM are equivalent to Turing machines. There is a subtlety with RAM: the registers are not finite registers, they are “variable-sized” registers that can accommodate numbers that are as large as needed for the computation. In practice, most concrete machines are like that — a register or memory cell is as large as it takes to store a pointer, and if the size of a pointer exceeds the register size, it means that you've overflowed the memory of your machine and you start the computation again on a machine with more memory and bigger registers.
> 9 votes

# Answer
I know this is an old thread, but I feel this answer can add some to the question.

I recently implemented a virtual machine that uses only a single stack, but is Turing complete: the thing that makes this work is simply one instruction, which moves the element at the bottom of the stack to the top. This allows access to any given variable on the stack at any time, and is based on the idea that in Brainf\**k, pushing to a stack is equivalent to \> and incrementing to a particular value (if the stack is used as BF's tape), while moving a variable from the bottom of the stack to the top (giving access to an otherwise inaccessible variable) is equivalent to \<.

Another way I have seen this done is by adding an instruction to swap the top variable with any other stack variable (again giving access to any arbitrary variable).

Both of these, with a carefully selected set of other instructions, can allow a stack-based machine to be Turing complete with only one (modified) stack.
> 2 votes

---
Tags: turing-completeness, interpreters
---


# Question
Title: Finding many different minima of nonlinear cost function
Given a nonlinear cost function $G(\vec{x})$ of many variables, does there exist a method that allows one to find successive local minima $\vec{x}\_0, \vec{x}\_1, \dots$ so that $\vec{x}\_n$ is orthogonal to $\vec{x}\_{n-1}, \vec{x}\_{n-2}, \dots, \vec{x}\_0$?

Sorry for the apparent lack of effort on my part, but the field of optimization is vast and I do not have a lot of experience. I have searched for variants of a nonlinear conjugate gradient method that have the above property, but haven't been able to find anything.

# Answer
> 1 votes
Suppose you have already found $x\_0,\dots,x\_{k-1}$ and now your goal is to find $x\_k$. Let $\mathcal{R}$ denote the region of points that are orthogonal to $x\_0,\dots,x\_{k-1}$. Then your problem is to minimize $G(x\_k)$ subject to the requirement $x\_k \in \mathcal{R}$. This is a straightforward equality constraint in optimization, and can be handled in a number of ways. Probably the simplest is to use projected gradient descent, which is like gradient descent but in each step you project the point onto the hyperplane $\mathcal{R}$. Given how you have defined $\mathcal{R}$, the projection operation in this case is easy.

---
Tags: optimization
---


# Question
Title: How to use Latin hypercube sampling with fixed points?
I use Latin hypercube sampling to select what point to evaluate my function. As evaluations take a lot of time, I want to limit the time by adding already evaluated points.

I thought about taking the min distance between the points, and if I have an already evaluated point that is near on LHS point, I remove the LHS to minimize the number of evaluations. Sadly this is not how LHS works, and the results are not very good.

# Answer
> 1 votes
You've divided the x values into 10 columns, and divided the y values into 10 rows, so we have a 10x10 grid.

Take any row that is already covered by some already evaluated point, and remove it from the set of rows. Do the same with the columns. In your picture, we are left with 6 rows and 6 columns. Consider the 6x6 grid obtained by looking only at those 6 rows and 6 columns.

Now use your Latin hypercube sampling strategy on a 6x6 grid, to cover each of those 6 rows and each of those 6 columns. This gives you 6 points that cover the 6x6 grid. Now this can be interpreted as 6 points in the 10x10 grid, and if you combine those 6 points with the 4 existing points, you'll see that the result covers every row and every column exactly once.

---
Tags: sampling, python, evaluation-strategies
---


# Question
Title: Is $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$?
We know that $\mathsf{DSPACE}(\log\log n) = \mathsf{DSPACE}(1)$ according to this proof. Can we claim that $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$ or something like $\mathsf{DSPACE}(n^3)=\mathsf{DSPACE}(n^3/(\log\log n)^k)$ for some $k\in \mathbb{N} $?

# Answer
> 3 votes
The space hierarchy theorem shows that your classes are different.

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


title: Minimum-weight shortest-path tree

text:
# Question
Title: Minimum-weight shortest-path tree
How can we compute the shortest-path tree of minimum total weight for a given connected graph?

I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one shortest-path tree with different total weights.

The above picture shows one such example (where $a$ represents the starting vertex).

Is there a way to find the shortest-path tree of minimum total weight without inspecting every possible shortest-path tree?

# Answer
Dijkstra's algorithm will not allow you to obtain such minimum-weight shortest-path tree due to its greedy nature: once it obtains the shortest path to a vertex, the algorithm never reconsiders this vertex again.

One possible approach to obtain such a tree is to apply a small extension to Bellman–Ford's algorithm. Whenever there is a tie in step 2 of the algorithm $-$ that is, whenever there is a tie between (1) a newly computed distance between the starting vertex $s$ and a vertex $v$, and (2) the current best shortest path between $s$ and $v$ $-$ compute how much weight each of the two shortest path candidates adds to the current tree (and keep the path that minimizes this value). The current tree is available in the *predecessor* array, which stores the tree as an array of parent pointers.

Applying the above solution, you are, in effect, checking all possible shortest paths, so I presume that the answer to your last question is no.
> 3 votes

# Answer
The minimum-weight shortest-path tree can be computed efficiently \[1\].

> The *shortest-path subgraph* in a rooted, weighted, directed graph is obtained from the graph by removing those edges $(u, v)$ *not* on any shortest path from the root — those for which $D\_{T\_S}(r, u) + w(u, v) \> D\_{T\_S}(r, v)$. It is easily shown that paths from $r$ in the shortest-path subgraph correspond to shortest paths from $r$ in the original graph, and vice versa.

*Proof*. Call the original graph $G = (V, A)$ and the shortest-path subgraph $G' = (V', A')$.

Let $(v\_0, v\_1, \dots, v\_k)$ be a path from $v\_0 = r$ to $v\_k = v$ in $G'$. If $k = 0$ then the path contains no edges and is thus trivially a shortest path in $G$. For $k \> 0$, if all paths of length $k - 1$ from $r$ in $G'$ correspond to shortest paths from $r$ in $G$, then in particular $(v\_0, v\_1, \dots, v\_{k - 1})$ is a shortest path from $r$ to $v\_{k - 1}$; that is, $\sum\_{i = 1}^{k - 1} w(v\_{i - 1}, v\_i) = D\_{T\_S}(r, v\_{k - 1})$. If our path to $v$ is not a shortest path then $$ D\_{T\_S}(r, v) \< \sum\_{i = 1}^k w(v\_{i - 1}, v\_i) = \sum\_{i = 1}^{k - 1} w(v\_{i - 1}, v\_i) + w(v\_{k - 1}, v\_k) = D\_{T\_S}(r, v\_{k - 1}) + w(v\_{k - 1}, v). $$ This contradicts the assumption that $(v\_{k - 1}, v) \in A'$. Since $(v\_0, v\_1, \dots, v\_k)$ was an arbitrary length-$k$ path, this shows by induction that paths from $r$ in $G'$ correspond to shortest paths from $r$ in $G$.

Conversely, let $(v\_0, v\_1, \dots, v\_k)$ be a shortest path from $v\_0 = r$ to $v\_k = v$ in $G$. If $k = 0$ then the path contains no edges and is thus trivially a path from $r$ in $G'$. For $k \> 0$, if all shortest paths of length $k - 1$ from $r$ in $G$ correspond to paths from $r$ in $G'$, then in particular $(v\_0, v\_1, \dots, v\_{k - 1})$ is in $G'$; that is, $(v\_{i - 1}, v\_i) \in A'$ for all $i \in \\{1, 2, \dots, k - 1\\}$. Thus if our path to $v$ is not in $G'$ then it must be the case that $(v\_{k - 1}, v) \notin A'$, so $$ \sum\_{i = 1}^k w(v\_{i - 1}, v\_i) = \sum\_{i = 1}^{k - 1} w(v\_{i - 1}, v\_i) + w(v\_{k - 1}, v\_k) = D\_{T\_S}(r, v\_{k - 1}) + w(v\_{k - 1}, v) \> D\_{T\_S}(r, v). $$ This contradicts the assumption that $(v\_0, v\_1, \dots, v\_k)$ is a shortest path in $G$. Since this was an arbitrary length-$k$ shortest path, this shows by induction that shortest paths from $r$ in $G$ correspond to paths from $r$ in $G'$.

> A *branching* in a rooted, directed graph is a spanning tree with all edges directed away from the root. Efficient algorithms for finding minimum-weight branchings are known \[2\].

This specifically refers to an implementation of Edmonds' algorithm using Fibonacci heaps.

> Thus, finding a minimum-weight shortest path tree in a directed graph reduces to finding a minimum-weight branching in the shortest-path subgraph. To find the minimum-weight shortest path tree in an undirected graph, simply direct it: duplicate each edge, directing one copy of each endpoint. Shortest-path trees in the original graph, directed appropriately, then correspond to shortest-path trees in the directed graph.

# References

\[1\] S. Khuller, B. Raghavachari, and N. Young. Balancing minimum spanning trees and shortest-path trees. *Algorithmica*, 14(4):305–321, Oct 1995.

\[2\] H. N. Gabow, Z. Galil, T. Spencer and R. E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, *Combinatorica*, 6 (2), pp. 109-122, (1986).
> 2 votes

---
Tags: algorithms, graphs, trees, shortest-path
---


# Question
Title: Understanding facts about regular languages, finite sets and subsets of regular languages
I am aware of following two facts related to two concepts: regular languages and finite sets:

> * Regular languages are not closed under subset and proper subset operations.
> * It is decidable whether given regular language is finite or not.

However I feel these facts are quite insufficient to prove whether following statements are true or false:

1. If all proper subsets of $L$ are regular, then $L$ is regular.
2. If all finite subsets of $L$ are regular, then $L$ is regular.
3. If a proper subset of $L$ is not regular, then $L$ is not regular.
4. Subsets of finite sets are always regular.

I feel 3 is false, as regular languages are not closed under proper subset operation. Right?

But I am unsure of the other points. What facts I am missing to answer above statements true or false?

# Answer
> 4 votes
One useful fact about regular languages is that *a union of finitely many regular languages is regular*. From this it follows that all finite languages are regular: the language that recognizes a single constant string is always regular, and a finite language is a union of finitely many constant strings.

(Proof: remember that regular languages are exactly those representable by regular expressions. A regular expression can be trivially written to recognize a single constant string. To recognize a finite union of regular languages, simply combine their regular expressions with the union operator. Now you have a (potentially enormous but) finitely-long regular expression recognizing the entire language.)

This means that 1 is true, because a finite set is equal to the union of all its proper subsets, and an infinite language always has a non-regular subset.

(Proof: if a language $L$ is finite, then it has finitely many subsets, and is equal to the union of these subsets. If $L$ is infinite, then it has uncountably many subsets. But there are only countably many regular languages over a given alphabet, because regular expressions are strings and thus can be enumerated. Thus by diagonalization there exists a non-regular subset.)

2, on the other hand, is false as long as there exists an infinite non-regular language. (And such a language does exist: $\\{ 0^n 1^n | n \in \mathbb{N} \\}$ is a classic example.) It's not regular, but all its finite subsets are finite, and thus regular.

Your intuition is correct: 3 is false. The non-regular language I just mentioned is a proper subset of $\\{ 0^a 1^b | a, b \in \mathbb{N} \\}$, which is regular.

4 is also true, since any subset of a finite set is always finite.

---
Tags: formal-languages, regular-languages, finite-sets
---


# Question
Title: Where do transformational grammars stand in the Chomsky Hierarchy?
From what I understand, natural language are too complicated to be generated by a context-free grammar, yet parsing a context-sensitive grammar is too computationally demanding for our brain to be continuously performing. So it seems that if our brain indeed has a "syntax" module to parse sentences as Chomsky claims it does, then whatever it's doing should sit somewhere between CFGs and CSGs in terms of computational complexity.

I'm really not familiar at all with Linguistics in general and even less so with Chomsky's work, but (correct me if I'm wrong) the point of transformational grammars was to explain this?

For those not familiar, a transformational grammar consists of a CFG to generate syntactically valid sentences, and also on top of this "transformational" rules, that transform these valid trees to form other valid trees. A common example is affirmative-\>question transformation ("John has eaten all the heirloom tomatoes." -\> "Has John eaten all the heirloom tomatoes?").

It is not clear to me why such tree transformations couldn't be integrated into the CFGs by adding more rules (for example, question-form sentences can clearly be generated instead of being transformed from an affirmative sentence).

If I am right (in that transformational grammars sit between CFGs and CSGs), could someone give me an example showing both relations (that TGs are more expressive than CFGs but less expressive than CSGs). If I'm wrong, then please help me increase my knowledge of linguistics by pointing me towards valid readings.

# Answer
I was taught in linguistics class that Chomsky abandoned his original arbitrary transformations after they were found to produce Turing completeness. See e.g. the Oxford Handbook of Linguistic Interfaces, p. 543; I am unable to locate the original reference.

He subsequently developed a formalism with more restricted transformations; the version I was taught was called *Government and Binding Theory*.

Some details are in Wikipedia under Transformational grammar.

While searching for references, I ran into a highly readable article on this matter by Geoffrey Pullum, which rejects Chomsky's original notion of transformations for purely linguistic reasons.
> 1 votes

---
Tags: formal-grammars, computational-linguistics
---


# Question
Title: DFA for Strings with third symbol from RHS as 1
How can we make a DFA for given condition in title from alphabets {0,1} (binary).

What can be the regular expression for this?

My calculated expression is **(a+b)\*a(a+b)(a+b)** , please correct me if i'm wrong and help find the correct expression and it's DFA.

# Answer
You probably want to substitute $a$ with $1$ and $b$ with $0$ but apart from that your solution is correct.

Finding an equivalent NFA is easy with Thompson, Glushkov etc. From that you can derive an DFA via powerset construction. However, for this short expression you also can just write the DFA down. Imagine the states as storage what the last 3 symbols were, and accept if the third last was a 1, i.e. name the states 000 to 111 where 000 is the initial state and all states with a leading 1 are accepting. A transition is just a shift-left with the last read symbol on the right, i.e. $\delta(abc, d) = bcd$, with $a,b,c,d \in \\{0,1\\}$.
> 3 votes

# Answer
Your regular expression is correct.

For a DFA, in this case it's easier to *define* it than to *draw* it. Formally, defining a DFA means choosing an alphabet, a state set, a start state, an accepting set, and a transition function.

Alphabet: $\Sigma = \\{0,1\\}$ as specified.

State set: The states are ordered triples $(x,y,z)$ where $x$, $y$, and $z$ are either 0, 1, or Null. These represent the last three symbols seen.

Start state: Start in state (Null, Null, Null). We haven't seen any symbols yet, with Null meaning "no symbol seen yet".

Accepting set: A state $(x, y, z)$ is accepting if $x$ is 1. That is, we accept if the third symbol from the end was a 1.

Transition function: If you're in state $(x, y, z)$ and you see symbol $s$, you transition into state $(y, z, s)$.

This fully defines the DFA, without needing to draw it out (which is more complicated for this question).
> 1 votes

# Answer
Check this out , it's not neat but it will get the work done. Correct me if i'm wrong in this DFA.
> -1 votes

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


# Question
Title: Definition of "properly partial" versus "total" value types
In the Foundations chapter of Elements of Programming (Stepanov and McJones, 2009), this paragraph appears:

> A value type is *properly partial* if its values represent a proper subset of the abstract entities in the corresponding species; otherwise it is *total*. For example, the type `int` is properly partial, while the type `bool` is total.

I have a hard time understanding what this means and have been unable to find any good explanations of these terms on the Internet. What are properly partial and total value types?

# Answer
$ \newcommand{\llbracket}{\[\\!\[} \newcommand{\rrbracket}{\]\\!\]} $First, a *proper subset* is a subset that is not equal to the whole set. In other words, $A$ is a proper subset of $B$ iff $A \subseteq B$ and $A \ne B$.

If you formulate a denotational semantics for a language, then each type $T$ has an associated set $\llbracket T \rrbracket$ which is called the *denotation* of $T$. Stepanov and McJones calls this set the *abstract species* corresponding to the type $T$ (in this particular semantics). For example, it is natural to associate the set of integers $\mathbb{Z}$ to the type $\mathtt{int}$, with value semantics $\llbracket \mathtt{0} \rrbracket = 0$, $\llbracket \mathtt{1} \rrbracket = 1$, $\llbracket \mathtt{-1} \rrbracket = -1$, etc. and the set of truth values $\\{\mathsf{T},\mathsf{F}\\}$ to the type $\mathtt{bool}$ with value semantics $\llbracket \mathtt{false} \rrbracket = \mathsf{F}$ and $\llbracket \mathtt{true} \rrbracket = \mathsf{T}$.

A type is *total* under a denotational semantics iff the set of denotations of values of that type is equal to the denotation of the type. A type is *properly partial* iff is it not total, that is, iff the set of denotations of values is a proper subset of the denotation of the type. (The denotation of a value must be a member of the denotation of the type, otherwise the semantics is not valid, thus the denotations of values always form subset of the denotation of the type.)

For example, the set of denotations of values of the type $\mathtt{bool}$ under the semantics above is $\\{\llbracket \mathtt{false} \rrbracket, \llbracket \mathtt{true} \rrbracket\\} = \\{\mathsf{F}, \mathsf{T}\\} = \llbracket \mathtt{bool} \rrbracket$ so the type $\mathtt{bool}$ is total under this semantics. On the other hand, the set of denotations of values of type $\mathtt{int}$ consists only of values in the range $\[-2^{N-1}, 2^{N-1}-1\]$, assuming a typical implementation of the type $\mathtt{int}$ with $N$ bits, therefore $\mathtt{int}$ is properly partial under this semantics.

Note that the totality of a type depends on the chosen semantics. For example, under a semantics where the denotation of $\mathtt{int}$ is the integer range $\[-2^{N-1}, 2^{N-1}-1\]$, the type $\mathtt{int}$ is total.

”Abstract species“ and “properly partial” are not widespread terminology. As far as I know, they were coined by these authors.
> 4 votes

# Answer
As Gilles implies in his answer, *properly partial* types come about mostly from the need to model infinite concepts using either finite representations or finite computations (i.e., finite both in workspace and in runtime).

The space of integers is infinite, but computer memory is always finite, so even arbitrary precision integer libraries will have a maximum amount of memory that they can allocate to the length of binary numbers, suggesting that all attempts to encode the integers on computers will always result in types that are at best properly partial.

Carrying these definitions forward brings us to such terms as *partial* or *nontotal procedures* and *total procedures*, and the need for *definition-space predicates* to guard procedures that are nontotal (to confirm as a precondition that the inputs are within the definition space of the procedure, so that, e.g., operations don't overflow).

> "Implementations of some total functions are nontotal on the computer because of the finiteness of the representation. For example, addition on signed 32-bit integers is nontotal."
> Elements of Programming, Chapter 2

All of this is also somewhat related to *value types* as correspondences between *species* and *datums*, where a *datum* is a finite sequence of 0s and 1s. A datum is a *representation* of an entity, and the entity is the *interpretation* of the datum. The datum together with its interpretation is a *value*. A datum is *well formed* with respect to a value type iff that datum represents an *abstract entity*.

> For example, every sequence of 32 bits is well formed when interpreted as a two's-complement integer; an IEEE 754 floating-point NaN (Not a Number) is not well formed when interpreted as a real number.
> — Elements of Programming, Chapter 1
> 1 votes

---
Tags: type-theory, discrete-mathematics
---


# Question
Title: Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k
Say I had a list of numbers in the range of 1-20 for example: \[5, 16, 17, 3, 2, 14, 4, 9, 11, 19\], and an integer k (let's say k = 40)

How would I find the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k?

I believe this algorithm is NP complete.

Just think of the problem as a bin packing algorithm but instead of saying that the total value of items in the bin must not exceed the bin's capcacity, I am saying that the total value of items in the bin must be exactly equal to the bin's capacity. Also, we are trying to maximise the number of bins.

Example scenario:

Say I have a list: \[1, 2, 2, 3, 5, 6, 5\] and k=7, then some example values of S would be:

\[(3+2+2), (6+1)\] - 5 and 5 left over

\[(5+2), (5+2), (6+1)\] - 3 left over

As you can see, the second solution is optimal because it produces 3 partitions rather than 2.

# Answer
> 1 votes
This problem is NP-complete. Even testing whether there exists a single subset that sums to $k$ is NP-complete; that is known as the subset sum problem. Therefore, you should not expect any efficient solution to this problem.

If you are asking for any way to solve it, without regard to efficiency, one approach is to enumerate all possible subsets that sum to $k$, build a graph with an edge between each pair of subsets that are not disjoint, and search for a maximum independent set in this graph. Another approach would be to use integer linear programming; define the zero-or-one $x\_{ij}$ integer variable to be 1 if the $i$th subset includes the element $j$, and then add constraints to reflect the problem statement, i.e., $\sum\_j x\_{ij} j = k$ and $x\_{ij} + x\_{i'j} \le 1$ for all $i\ne i'$. Then, apply an off-the-shelp ILP solver.

---
Tags: combinatorics, packing, subset-sum
---


# Question
Title: Proving that an equal partition does not exist
We are given a set of $n$ numbers and want to know whether it can be partitioned to two sets with an equal sum.

To prove that an equal partition exists, it is sufficient to show a partition.

What is the shortest way to prove that an equal partition does NOT exist? Apparently the only way to prove it is to show all the partitions and show that they are not equal. Is there a shorter proof?

# Answer
The current expectation is that most likely there is no efficient (polynomial-size, polynomially-verifiable) way to do that.

The partition problem is NP-complete. For a NP-complete problem, we have an efficient way to certify that the answer to the question is YES, but not necessarily any efficient way to certify that the answer is NO. If you find an efficient way to verify that the answer is NO (i.e., a polynomial-length proof that can be verified in polynomial time), then you have proven that the problem is in co-NP. If you prove that any NP-complete problem is in co-NP, then you have proven NP = co-NP. Currently, it is widely conjectured that NP $\ne$ co-NP. Assuming that conjecture is correct, there is no polynomial-length polynomially-verifiable proof that an equal partition does not exist.
> 7 votes

---
Tags: np-complete, partitions
---


# Question
Title: How can I optimize 3 variables in order to maximize the end product?
I am in the process of making a cryptocurrency trading bot. Currently, I am doing backtesting over a period of 7 months in which I provide a portion of historical data as if it were in real-life.

By modulating 3 variables: decision threshold, maximum % gain per trade, and stop loss, I want to find the best input values in order to maximize the amount of ending money I have at the end of the backtest.

What would be a good way to go about this? Currently, I'm running each backtest, and changing only 1 variable, but it seems like a slow process and I feel like there has to be a better way to do it. I've heard about neural networks, but I'm not 100% sure this would be a good scenario to apply that here.

# Answer
> 3 votes
This area is known as black-box optimization: you have a function $f(x,y,z)$ where you have the ability to evaluate $f$ on an input of your choice, and you want to find $x,y,z$ that maximizes $f(x,y,z)$. (Here $x$ is the decision threshold, $y$ is the maximum % gain per trade, and $z$ is the stop loss, and $f(x,y,z)$ is the amount of ending money at the end of a backtest with those parameters.)

There is a broad literature on black-box optimization, with many methods you could try. See, e.g., Google Vizier, BBComp, and derivative-free optimization; there are many other resources as well.

One last warning: your current procedure is likely to greatly overfit. If you get a rate of return of 10% on your historical data, that doesn't mean this is expected to give you a rate of return of 10% on future data; the future return rate will probably be far lower, due to overfitting. If you want to estimate the likely future rate of return, I suggest you split your historical data into a training set and a validation set (e.g., 4 months into the training set, 3 months into the validation set). Use the training set for the backtesting and to select the parameters. Then, once you have picked a value for the parameters, you can measure how well it performs on the validation set. To avoid bias, you're only allowed to use the validation set once -- if you don't like the results you get on the validation set, you're not allowed to go back to the training set and try to choose new parameters.

Personally, I suspect that 7 months won't be nearly enough. There are financial behaviors that only occur once every few years (e.g., due to financial cycles that occur on a multiple-year horizon), so it's likely that optimizing based solely on 7 months of historical data could lead you to parameters that might perform badly when the situation changes.

---
Tags: neural-networks, python
---


title: Can an algorithm run in "O(n/a)" time?

text:
# Question
Title: Can an algorithm run in "O(n/a)" time?
**On one hand,** it seems to make no sense, because of the following:

When expanded, the claim $f(n,a) \in O(n/a)$ would be

> There exist $C \> 0$, $n\_0$, and $a\_0$ such that if $n \geq n\_0$ and $a \geq a\_0$, then $f(n,a) \leq C \cdot n/a$.

Now, given any $\epsilon \> 0$, we can find an $a\_\epsilon \geq a\_0$ such that $C \cdot n\_0/a\_\epsilon \< \epsilon$, and thus $f(n\_0, a\_\epsilon) \< \epsilon$.

So for any $\epsilon$, there is an input, with $n = n\_0$ and $a = a\_\epsilon$, at which the algorithm takes less than $\epsilon$ time to run. But any nontrivial algorithm performs at least one operation, regardless of the input. So this seems nonsensical.

**On the other hand,** you can imagine someone saying that some approximation algorithm runs in time "$O(n/a)$", where $n$ is the size of the input and $a$ is the maximum multiplicative error.

And in fact, there is a paper in which an algorithm is claimed to run in "$\tilde{O}(\frac{n}{A^3 \epsilon})$" time. (Yes, I know $\tilde{O}$ is different from $O$). I asked a longer question about that here. This question is an attempt to isolate the core confusion there.

# Answer
For approximation algorithms, the algorithm must return an answer within a factor of $1\pm\epsilon$ of the true value. As such, smaller values of $\epsilon$ correspond to better approximations. As such, a running time that's polynomial in $n$ and $1/\epsilon$ is what you'd intuitively look for: it's saying that a better approximation (smaller $\epsilon$, so larger $1/\epsilon$) will take more time, but not by an unerasonable amount.

Also, note that we typically have an upper bound on $\epsilon$. For example, suppose we want to approximately compute the distance between two distinct vertices in a connected graph. We know the distance must be between $1$ and $n$ the number of vertices) so if we just want an approximation within $1\pm\epsilon$ and $\epsilon\ge\sqrt{n}$, we can just return $\sqrt{n}$.
> 4 votes

# Answer
The interpretation is closer to the following:

> There exists $C\>0$ such that for all $n,a$, $f(n,a) \leq C(n/a)$.

But this is also not quite right, since not all values of $n,a$ make sense.

Taking a look at the actual paper, we see that Algorithm IV calls Algorithm V with the parameter $B = A/2\sqrt{\log(2/A\epsilon)}$.

Algorithm V, in turn, tacitly assumes that $B^2 \leq n$ (note that confusingly enough, they use $A$ instead of $B$ for the approximation parameter). This means that $A$ is constrained to satisfy $$ \frac{A}{2\sqrt{\log(2/A\epsilon)}} \leq \sqrt{n}. $$

The running time of Algorithm IV is stated in full in Lemma 6: $$ O\left(\frac{n}{A^3 \epsilon} \log^2 \frac{1}{A\epsilon}\right). $$ This means that there exists a constant $C$ such that the running time is at most $$ C\frac{n}{A^3 \epsilon} \log^2 \frac{1}{A\epsilon}, $$ for all $A,\epsilon,n$ satisfying $$ \frac{A}{2\sqrt{\log(2/A\epsilon)}} \leq \sqrt{n}. $$ (There might be additional constraints that I missed.)

This is the meaning of $\tilde{O}(\frac{n}{A^3\epsilon})$ for Algorithm IV.
> 4 votes

---
Tags: complexity-theory, asymptotics
---


# Question
Title: How can I complete my derivation of an algorithm to solve Sudoku puzzles from my formalisation of the rules?
I'm hoping to design and implement an intuitive algorithm that solves 9x9 Sudoku puzzles. I want to do this by first formalising the basic rules of the puzzle, and then deriving principles from these that when followed should be sufficient for solving the problem. I have reproduced my (very rough) work below.

```
Rule 1: Each box must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in box b, then val(i, j) = v
----- At most one instance: If val(i, j) = v in box b, then for all (i2, j2) in box b, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 2: Each row must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in row r, then val(i, j) = v
----- At most one instance: If val(i, j) = v in row r, then for all (i2, j2) in row r, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 3: Each column must contain one instance of each of the numbers 1 to 9:
----- At least one instance: If (i, j) is only possible location of v in column c, then val(i, j) = v
----- At most one instance: If val(i, j) = v in column c, then for all (i2, j2) in column c, if (i != i2 || j != j2) then val(i2, j2) != v

Rule 4: Each cell must contain exactly one number:
----- At least one number: If (i, j) cannot contain any value except v, then val(i, j) = v
----- At most one number: If val(i, j) = v1 && val(i, j) = v2, then v1 = v2

```

However, I have run into a problem. Having solved Sudoku puzzles of various difficulties myself, I am aware of other principles that may need to be followed to solve a given puzzle. For instance:

```
----- If v must occur in one of two or three cells in box b, and these cells fall in the same row r, v cannot occur anywhere else in r.
----- If v must occur in one of two or three cells in box b, and these cells fall in the same column c, v cannot occur anywhere else in c.

```

These examples look like weaker versions of principles I have already written above, but I am having a hard time trying to derive them from the rules, since I want to be rigorous rather than simply adding principles ad hoc.

If anyone could give me a hand by showing me how I can go about deriving these more complex principles rigorously from the rules (ensuring that nothing is missed), I would be grateful. Thanks.

# Answer
One method of dealing with these, somewhat, emergent rules is constraint solving. You can iterate through each cell and place constraints on other squares based on that cell.

For example, if a square is 3, you can place a "cannot be 3" constraint on all other squares in its row, column, and 3x3 box. The two examples you provided can be solved once you place all the constraints, and look at what options are available.

This sort of method is very similar to what you would do when solving a sudoku puzzle when you write down the possible numbers in each square, and fill a box in when there is only one possibility.
> 0 votes

---
Tags: algorithms, sudoku
---


# Question
Title: optimize string search on black-box function
Given a lower-bound predicate function which returns `true` if an input is greater than or equal to a constant string, what is the optimal way to search for the constant? The strings should be lexicographical compared.

For example, given a handle to the following function, but not knowing the specific constant used:

```
fn lower_bound(s: &[u8]) -> bool {
    s >= &[10, 20, 30]
}

```

What is the optimal algorithm for determining the enclosed value of `&[10, 20, 30]`? A maximum length for the value can be assumed if that makes it more tractable.

# Answer
The most optimal algorithm would be to perform a binary search for each character sequentially (bin-search for 1st char, bin-search for 2nd char, ...etc).
> 2 votes

---
Tags: algorithms, optimization, strings
---


# Question
Title: A Recursive Formula For Generalized Josephus problem
The Josephus Problem asks where to start taking out every kth person in the circle consisted of n people, such that you are the last "survivor".

The following recursive formula is given: $$\begin{align} f(1,k)&=1, \\ f(n,k)&=((f(n-1,k)+k-1) \bmod n )+1. \end{align}$$

But this is not enough explanation, so I don't get where does it come from.

Can anyone help?

# Answer
> 4 votes
Let me explain the idea. Assume that indices start from 0. Take N = 6 and K = 3 So initial arrangement looks something like

> 0-\>1-\>2-\>3-\>4-\>5-\>0.... like a circle.

After round 1 , '2' is eliminated .

> 0-\>1-\>2-\>3-\>4-\>5-\>0-\>1...
>
> `....(k)->0->1->2->3->`
>
> > here (k) denotes the person is killed

Since we ought to start from the last position we killed, so lets look at the updated indices.

> `Old Index` | `New Index`
>
> > `3` | `0`
> >
> > `4` | `1`
> >
> > `5` | `2`
>
> and so on.... looking closely we can easily see after each round
>
> > `OldPosition = (newPosition+k)mod N`

Where N is the number of people left before the round started.

Also `OldPosition` signifies `f(N,K)`

and `New Position` signifies `f(N-1,K)` as one person has already been killed.

So putting it back to `OldPostion = (newPostion+k) mod N` we get

`f(N,K) = ( f(N-1,K)+ K ) mod N`

But this is done only if u have indices starting from 0. If u want to rearrange for indices starting from 1, you can rearrange it to get the above result.

I found a beautiful paper on this

http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf

Hope this helps :)

# Answer
> 1 votes
Knuth goes through this in the first chapter of his classic math textbook, Concrete Mathematics. His treatment is very understandable.

---
Tags: combinatorics, recursion
---


title: "Or" in regular expressions

text:
# Question
Title: "Or" in regular expressions
I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it.

One basic problem I wanted to solve was defining the minimal set of states need to construct a (minimal) DFA that accepts

$$(a^+)+bcd^\*\\,.$$

I'm not sure how to treat the OR operator here, though.

I assume it means I can accept either ($a^+$) OR $bcd^\*$ OR both (but in the given order), but does it mean I can ignore the order as well (meaning that, e.g. $bcdddaa$ would be acceptable as well)?

If anyone could explain, I would appreciate it. I understand the meaning of other operators.

# Answer
You're confusing "or" with concatenation. Also, In computer science, a string matching a regular expression means that the whole string matches whereas regular expressions used in computer software usually just require some part of the string to match the expression.

A string matches $a^+$ if the whole string is composed of $a$s and nothing else, and there's at least one $a$. A string matches $bcd^\*$ if it consists of a $b$ followed by a $c$ followed by zero or more $d$s and nothing else.

A string matches $a^++bcd^\*$ if it matches $a^+$ or it matches $bcd^\*$ or if it matches both. However, it's not possible to match both: a string can't be composed entirely of $a$s and also begin with a $b$ and a $c$.

In particular, $aabcdd$ doesn't match $a^++bcd^\*$ because it doesn't match $a^+$ (it contains characters that aren't $a$) or match $bcd^\*$ (it doesn't even begin with $b$). However, $aabcdd$ *does* match $a^+bcd^\*$, which is the concatenation of $a^+$ and $bcd^\*$. $bcddaa$ matches neither $a^++bcd^\*$ nor $a^+bcd^\*$.
> 1 votes

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


title: Algorithm for matching people

text:
# Question
Title: Algorithm for matching people
I work at a summer camp where one of the activities is called *Speed Dating*. It's a game where participants talk with each other for a fixed amount of time. At the end everyone has to list three people they liked the most.

I'm looking for an algorithm that would match participants based on their preferences. It seems like it's the Stable marriage problem that could be solved using Gale-Shapley algorithm. However every implementation of this algorithm I've seen assumes that the number of men and women is equal and every person has to rank everyone from the opposing gender.

**So my question is:**

How can I ensure that all "marriages" are stable given that:

* Participants are divided into two groups unequal in size
* Every participant provides a ranked list of only three people from the opposing group they like the most
* Some of the participants might list no people
* Not everyone has to be matched
* A "marriage" is stable only when two people have picked each other (regardless of their ranks)

# Answer
This is the problem of finding a matching in a bipartite graph. Each person is represented as a vertex in the graph, and you draw an edge between two people if they both have included each other on their rankings. Then any matching corresponds to a way to match people. There are standard algorithms that can find a maximum matching in a bipartite graph efficiently, so you'll even be able to find a pairing that maximizes the number of stable pairs created.
> 2 votes

---
Tags: algorithms, matching
---