title: The $\text{k-key}$ problem

text:
# Question
Title: The $\text{k-key}$ problem
Given an undirected graph, I define a structure called *k-key* as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well.

Here's the *k-key problem*: given an undirected graph $G$ and a number $k$, decide whether $G$ contains k $k$-key.

I want to show that the k-key problem is a NP-complete.

I want to make a reduction from the 'Undirected Hamiltonian Cycle' problem in which the input is a graph, and the problem is to decide whether it contains a Hamiltonian path. I already know that this problem is NP-complete. The input for the reduction would be an undirected graph $G$ and the output is $G'$ graph and $k$. Can you please help me understand what manipulation I should do to the original graph in order to show this reduction? And why should it work?

# Answer
You want to find a way of creating $G'$ from $G$ such that $G'$ has a $k$-key iff $G$ has a Hamiltonian path.

If a graph $G$ has $k$ vertices and a simple path of length $k$, then what can we conclude about it having a Hamiltonian path?

I'm guessing the intention is that the vertices in the path must be different from the vertices in the cycle (otherwise every ham cycle graph would contain a $k$-key and vice versa). So just think, suppose we knew that $G$ had a ham cycle starting from some vertex. Where would we tack on some vertices to create a $G'$ that had a $k$-key using $G$'s ham cycle?
> 3 votes

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


# Question
Title: Algorithm for type conversion / signature matching
I'm working on an expression typing system and looking for insights on what algorithms may be available which solve my problem -- or a proof that its complexity is too high to be reasonable to implement. The problem is defined below.

I have a set of types which form a directed graph $T = (V,E)$ (assume no cycles). This graph represents the allowed type conversions in a language. For example an edge $e\_i = v\_1 \rightarrow v\_2$ indicates that $v\_1$ can be implicitly converted to type $v\_2$.

I have a set of parameter types for a function expressed as a set $P = { p\_1 ... p\_n : p\_i ∈ V }$. I also have a list of functions $F$ that might be applicable at this point. Each function has a signature (the types it accepts) $F\_j = { f\_1 ... f\_n : t\_i ∈ V }$.

The goal is to use a series of type conversions allowed by $T$ to convert $P$ into a signature compatible with any function in $F$. Conversion means moving along an edge in the graph to another type. Compatible means the converted parameter types match the function types.

If each conversion has a cost of 1, which function, if selected, has the minimum total conversion cost for all parameters?

---

*A very simple example*: Assume we have a graph of types `integer -> real -> complex`. Our parameters have the types `{ integer, real }`. We have a function with types `{ complex, complex }`. The first integer takes two conversion to match complex, and the real takes one conversion, for a total cost of three. We have another function with types `{ real, real }`. This has a cost of one and is thus the better match.

---

My initial idea is to treat the search as a path through a graph and use a modified A\* algorithm. Each of the possible functions is a goal in that graph, and each path between nodes represents the conversion of a single parameter type. With even a modest number of allowed type conversions however this becomes very inefficient.

# Answer
> 4 votes
I would suggest first solving the all-pairs shortest distance problem on the graph $T$ (or at least the single source version for each $p\_i$ as the source) using standard approaches. Then, for each function signature $F\_j=f\_1,\dots,f\_n$, compute $\sum\_{i=1}^nd(p\_i,f\_i)$, where $d(p,f)$ is the distance between $p$ and $f$ (which can be infinite if $f$ is not reachable from $p$), then take the function that achieves the minimum. You should be able to do this in $O(|V|^3+nm)$ if you have $n$ parameters and $m$ functions.

---
Tags: algorithms, typing
---


title: NP-completeness and NP problems

text:
# Question
Title: NP-completeness and NP problems
Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not in NP-complete? Or would this just shows the availability of a polynomial algorithm for each NP problem indirectly?

edit: I know that when NP-complete problems have polynomial algorithms, all NP problems must have polynomial algorithms. The question I am asking is that whether we can use the discovered algorithm for NP-complete to all NP problems just by modifying the algorithm. Or would we just know that NP problems must have a polynomial algorithm indirectly?

# Answer
> 5 votes
Recall a few definitions. A language $L \subseteq \\{0,1\\}^\*$ is polynomial-time reducible to a language $L' \subseteq \\{0,1\\}^\*$, often denoted as $L \leq\_p L'$, if there is a *polynomial-time computable* function $f : \\{0,1\\}^\* \to \\{0,1\\}^\*$ such that for every $x \in \\{0,1\\}^\*$, $x \in L$ iff $f(x) \in L'$. Now, $L'$ is $\text{NP}$-hard if $L \leq\_p L'$ for every $L \in \text{NP}$. $L'$ is $\text{NP}$-complete if $L'$ is $\text{NP}$-hard *and* $L' \in \text{NP}$.

It is easy to see that if $L$ is $\text{NP}$-hard and $L \in \text{P}$, then $\text{P} = \text{NP}$. Likewise, if $L$ is $\text{NP}$-complete, then $L \in \text{P}$ iff $\text{P} = \text{NP}$. The intuitive reason is that if $f$ and $g$ are functions that grow at most as $n^c$ and $n^d$ respectively, then the composition $f(g(n))$ grows at most $n^{cd}$, which is also *polynomial*.

Assume you found a polynomial-time algorithm $A$ for a $\text{NP}$-complete problem $X$. Now, you could in polynomial time transform another $\text{NP}$-complete problem to $X$ and solve it using $A$. This is why we often say that it suffices to study whether any $\text{NP}$-complete problem can be decided in polynomial time.

# Answer
> 0 votes
Here is one direct example:

The whole notion of NP-completeness came about when Cook and Levin and others discovered that it was possible to express the existence of an accepting path of computation in a non-deterministic Turing machine in a fairly straightforward manner as a Boolean expression as long as the length of the computation could be bounded.

So all of NP was **reduced** to the satisfiability of a certain Boolean expression that could easily be constructed from a hypothetical non-deterministic Turing machine whose running time could be bounded in a polynomial in the size of the input.

But the problem of the satisfiability of a Boolean expression is trivially in NP itself: simply assign all the variables non-determistically, evaluate the expression, and accept if it is true. There will be an accepting path of computation if and only if the expression is satisfiable. Therefore Boolean satisfiability is said to be NP-complete.

Likewise, for all existing problems known to be NP-complete, there is an explicit reduction that could be applied to solve any problem in NP in deterministic polynomical time if a suitable algorithm were found for that problem.

But the possibility of finding a polynomial algorithm for a problem known only indirectly to be NP-complete (without an explicit reduction) has not been ruled out, and this would be the case for any non-constructive proof that P=NP, since if P=NP then all problems in P are trivially NP-complete.

---
Tags: complexity-theory
---


# Question
Title: NP-Completeness of a Graph Coloring Problem
**Alternative Formulation**

I came up with an alternative formulation to the below problem. The alternative formulation is actually a special case of the problem bellow and uses bipartite graphs to describe the problem. However, I believe that the alternative formulation is still NP-hard. The alternative formulation uses a disjoint set of incoming and outgoing nodes that simplifies the problem definition.

Given $n$ outgoing and $n$ incoming nodes (the red and blue nodes in the figure respectively), and a set $w\_{ij}$'s of size $n \times n$ of edge weights between the outgoing and incoming vertices. The goal of the problem is to color the thick edges in the figure so that for every incoming node, a condition holds.

> Given a set $\\{ O\_i \\; | \\; i=1 \dots n \\}$ of output vertices, a set $\\{ I\_i\\; | \\; i=1 \dots n \\}$ of input vertices, $n \times n$ weights $w\_{ij} \ge 0$ between $O\_i$'s and $I\_j$'s for $i,j=1 \dots n$, and a positive constant $\beta$, find the minimum number of colors for the edges $e\_{ii}$ (thick edges in the above figure) such that for all $j=1 \dots n$,
>
> $$ \frac{w\_{jj}}{1+\sum\_{c(i)=c(j),i \neq j} w\_{ij}} \ge \beta $$
>
> where $c(i)$ shows the color of the edge $e\_{ii}$.

---

**Old Formulation**

The following problem looks NP-hard to me, but I couldn't show it. Any proof/comment to show the hardness or easiness of it is appreciated.

> Assume $K\_n=\langle V,E \rangle$ is a complete weighted directed graph with $n$ nodes and $n(n-1)$ edges. Let $w\_{ij} \ge 0$ show the weight of the edge $ij$ and $c(ij)$ shows the color of edge $ij$. Given a subset of the edges $T \subseteq E$ and a positive constant $\beta$ the goal is: find the minimum number of colors such that for each $e\_{ij} \in T$:
>
> $$ \frac{w\_{ij}}{1+\sum\_{c(kl)=c(ij),kl \neq ij} w\_{kj}} \ge \beta. $$ and $$ c(ij) \neq c(ik) \quad for \quad j \neq k $$

Please note that in the above problem, only the edges in $T$ needs to be colored. That is the problem can be solved in $\mathcal{O}(|T|!)$.

**Update:**

After Tsuyoshi Ito's comment I updated the problem. The denominator is changed from $1+\sum\_{c(kj)=c(ij),k \neq i,e\_{kj} \in T} w\_{kj}$ to $1+\sum\_{c(kl)=c(ij),kl \neq ij} w\_{kj}$. Therefore, the denominator contains the weights outside $T$ as well. That's actually why I mentioned the complete graph in the definition.

I also added an additional constraint $c(ij) \neq c(ik) \quad for \quad j \neq k$. That means, the outgoing edges from a node must be of different colors (but the incoming colors can be the same as long as the inequality holds). This puts an intuitive lower bound on the number of colors, which is the maximum out-degree of the nodes in $T$.

As Tsuyoshi mentioned, $w\_{ij}$'s, $T$, and $\beta$ are inputs to the problem and the edge colors are the output.

**Update 2:**

Problem does not enforce the edges $e\_{ij}$ and $e\_{ji}$ be of a same color.

# Answer
> 3 votes
It is quite simple to show that the alternative formulation is NP-hard. The reduction is from the vertex coloring problem. Given a graph G with $n$ vertices, we create an instance of the above problem with $n$ output vertices and $n$ input vertices. Weights are set as follows: For all $i$, let $w\_{ii}=1$. For $i \neq j$, if there is an edge between vertex $i$ and vertex $j$, let $w\_{ij}=w\_{ji}=1$, else let $w\_{ij}=w\_{ji}=0$. In addition, let $\beta=1$.

This is quite obvious but difficult to describe why the reduction is correct. Let $\mathcal{C}$ show the instance of the graph coloring and $\mathcal{R}$ show the reduced instance of the problem. To show the above reduction gives a correct solution we need to show that (1) every valid coloring for $\mathcal{R}$ is valid for $\mathcal{C}$ as well. (2) the answer given by $\mathcal{R}$ is minimal for $\mathcal{C}$.

If $i$ and $j$ are two adjacent vertices of $\mathcal{C}$, then they must have different colors in $\mathcal{R}$. That is because if $i$ and $j$ are adjacent and they have the same color, the fraction $\frac{w\_{jj}}{1+\sum\_{c(i)=c(j),i \neq j} w\_{ij}}$ would result in $\frac{1}{1+X}$, where $X$ has a positive value. Therefore, the condition does not hold. In addition, every valid (but not necessarily minimal) coloring for $\mathcal{C}$, is a valid coloring for $\mathcal{R}$ as well. It follows the fact that in a valid coloring of $\mathcal{C}$, every pair of adjacent nodes have different colors, so the condition holds for all the colored edges of $\mathcal{R}$ in the solution. Since every coloring of $\mathcal{C}$ is a valid coloring for $\mathcal{R}$, the minimal solution to $\mathcal{R}$ must be a minimal solution to $\mathcal{C}$ as well. Otherwise, it is not a minimal one because the solution to $\mathcal{C}$ gives a solution with a smaller number of colors.

# Answer
> 0 votes
**EDIT**: The construction below doesn't quite work, as per Tsuyoshi Ito's comment below, it doesn't enforce that $c(ij)=c(ji)$. I leave it up in case it's a useful start though. Also, $T$ shouldn't include arcs with weight $0$.

Along the lines Mohsen suggested, start with Edge Coloring, convert the graph $G=(V,E)$ to a digraph $D=(V,A)$ on the same vertex set where $\forall uv\in E$ we have $(u,v)$ and $(v,u)$ in $A$, give all arcs $a \in A$ (at this point) weight $w\_{a} = 1$, then $\forall xy \notin E$ add $(x,y)$ and $(y,x)$ to $A$ with $w\_{xy}=w\_{yx}=0$, set $\beta$ to $1$ and $T=A$.

Then the condition is only satisfied if no two arcs incident on the same vertex have the same colour, disregarding arcs that come from non-edges in the original graph (as they have weight $0$). This colouring can then be converted back to a proper colouring for the original graph.

Technically I've converted your original problem to a decision problem ("is the graph colourable with $k$ colours?"), but this needed to be done to fit into $NP$ anyway and it's effectively interchangable up to a polynomial.

So I think that works, or have I just shown something else to be $NP$-hard? ;)

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


# Question
Title: Vertex coloring with an upper bound on the degree of the nodes
Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices with minimum number of colors such that no pair of adjacent nodes have the same color) on this set still NP-hard? Why?

# Answer
> 5 votes
Yes, it's still NP-hard. 3-COL is still NP-complete for planar degree 4 graphs \[1\].

---

1. Dailey, D. P. (1980), "Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete", Discrete Mathematics 30 (3): 289–293, DOI:10.1016/0012-365X(80)90236-8

---
Tags: algorithms, complexity-theory, graphs, np-complete
---


# Question
Title: Time series probability and mutual information
There is a time series of say $100$ data points. I wish to assign symbols of $0, 1, 2$ for each unique data point. The issue is I have tried but got stuck since no matter I specify the symbols, the program just outputs probability of $1$'s and $0$'s. The following are the questions:

1. How to find probability or correct my code so that it outputs probablities when number of symbols size \> 2?
2. How to calculate entropy annd mutual information for this case. I don't know although I have read Matlab's entropy calculation Mutual Information & Entropy but alas cannot follow how to apply in this case.

# Answer
> 2 votes
Entropy is, in your case

```
probs = [p_0 p_1 p_2];
logProb = log(probs);
entropy = -1 * dot(probs, logProb);

```

You'll have to let us know what two random variables you want to calculate the mutual information of, but with your library it looks like you just need to call `mutualinfo(vec1,vec2)`.

---
Tags: probability-theory, information-theory
---


# Question
Title: Witness for the $EU(\phi_1,\phi_2)$ using BDDs
I wanted ask if you know an algorithm to find the witness for $EU(\phi\_1,\phi\_2)$ (CTL formula "Exist Until") using BDDs (Binary Decision Diagram). In pratice you should use the fixed point for calculating $EU(\phi\_1,\phi\_2)$, that is:

$\qquad \displaystyle EU(\phi\_1,\phi\_2)=\mu.Q (\phi\_2 \vee (\phi\_1 \wedge EX Q)) $

Unwinding the recursion, we get:

$\qquad \displaystyle \begin{align} Q\_0 &= \textrm{false} \\ Q\_1 &= \phi\_2 \\ Q\_2 &= \phi\_2 \vee (\phi\_1 \wedge EX \phi\_2) \\ \ \vdots \end{align}$

and so on.

To generate a witness (path) we can do a forward reachability check within the sequence of $Q\_i’s$, that is find a path

$\qquad \displaystyle \pi= s\_1 \rightarrow s\_2 \rightarrow \cdots \rightarrow s\_n$

such that $s\_i \in Q\_{n-i} \cap R(s\_{i-1})$ (where $R(s\_{i-1})= \\{ s \mid R(s\_{i-1},s) \\}$ and $R(s\_{i-1},s$) is the transition from $s\_{i-1}$ to $s$ ) where $s\_0 \in Q\_n $ and $s\_n \in Q\_1=\phi\_2$.

How you can do this with BDDs?

# Answer
> 3 votes
What you describe is symbolic model checking, and it is treated in this set of slides, using reduced ordered BDDs.

In a nutshell, you still do the fixpoint iteration, the main issue being how to do the transformation $Q\mapsto \phi\_2\vee(\phi\_1\wedge EXQ)$ on BDDs. The elementary operations you need are renaming (to replace unprimed by primed variables in $Q$, obtaining $Q'$), boolean operations (to form $\phi\_2\vee(\phi\_1\wedge R\wedge Q')$) and abstraction (to do existential quantifier elimination on the primed variables). The witness generation can then be done similarly forwards from the initial states, requiring at step $i$ that $s\_i$ is in $Q\_{n-i}$ as you did above.

---
Tags: formal-methods, model-checking
---


# Question
Title: Easy reduction from 3SAT to Hamiltonian path problem
There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem.

> Is there a simpler reduction?

By simpler I mean a reduction that would be easier to understand (for students).

> Is there a reduction that uses linear number of variables?

The reduction in Sipser uses $O(kn)$ variables where $k$ is the number of clauses and $n$ is the number of variables. In other words, it is possible for the reduction to blow the size from $s$ to $O(s^2)$. Is there a simple reduction where the size of the output of the reduction is linear in the size of its input?

If it is not possible, is there a reason? Would that imply an unknown result in complexity/algorithms?

# Answer
> 8 votes
The number of vertices in the well-known reduction from 3SAT to directed Hamiltonian Path(dHAMPATH) can be easily reduced to $O(n+k)$, where $n$ is the number of variables and $k$ is the number of clauses, therefore the size of the constructed graph instance is linear to the size of the original 3SAT instance.

In the original reduction, we have start vertex and end vertex, $k$ vertices for clauses, $n$ lists of length $4k$ for variables. The idea is that we don't have to construct list of length $4k$ for each variable, we can construct list according to the number that the variable appears in all the clauses. Since the total number of appearances of variables in clauses is $3k$, it is $O(n+k)$.

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


# Question
Title: Is the shadow ray in a Whitted ray tracer occluded by transparent objects?
In a Whitted ray tracer, each ray-object intersection spawns a transmitted ray (if the object was translucent), a reflected ray and a shadow ray. The shadow ray contributes the direct lighting component.

But what happens if the shadow ray intersects a transparent object? Is the direct lighting component ignored? How will diffuse objects submerged in water be lit if they don't get any direct light contributions from the shadow ray?

# Answer
> 2 votes
You should first refer to Rendering Equation. It is the general equation to describe the physically transmitting of light in the view of computer science.

Whitted model is just an approximation of the surface integration of the Rendering Equation. It only calculates three light rays(shadow ray, reflected ray, and refracted ray). In a more sophisticated ray tracer, you should use Monte-Carlo ray tracing, where at every intersection point on the object, you will use thousands of rays sampling according to BRDF. Such backward algorithms actually work not good at caustic scene, which is the scene you say. You can use Photon Mapping plus Monte-Carlo Ray Tracing to get a better visualization.

If you just want to use Whitted model, you can multiply the lighting of shadow ray by a factor defined by the occluded transparent object.

---
Tags: graphics
---


# Question
Title: Is Karp Reduction identical to Levin Reduction
### Definition: Karp Reduction

A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\\{0,1\\}^\*\rightarrow\\{0,1\\}^\*$ such that for every $x$, $x\in A$ if and only if $f(x)\in B$.

### Definition: Levin Reduction

A search problem $V\_A$ is Levin reducible to a search problem $V\_B$ if there is polynomial time function $f$ that Karp reduces $L(V\_A)$ to $L(V\_B)$ and there are polynomial-time computable functions $g$ and $h$ such that

1. $\langle x, y \rangle \in V\_A \implies \langle f(x), g(x,y) \rangle \in V\_B$,
2. $\langle f(x), z \rangle \in V\_B \implies \langle x, h(x,z) \rangle \in V\_A$

Are these reductions equivalent?

---

I think the two definitions are equivalent. For any two $\mathsf{NP}$ languages $A$ and $B$, if $A$ is Karp reducible to $B$, then $A$ is Levin reducible to $B$.

Here is my proof:

Let $x$ and $\overline{x}$ be arbitrary instances of $A$ while $x'$ be that of $B$. Suppose $V\_A$ and $V\_B$ are verifiers of $A$ and $B$. Let $y$ and $\overline{y}$ be arbitrary certificates of $x$ and $\overline{x}$ according to $V\_A$. Let $z$ be that of $x'$ according to $V\_B$.

Construct new verifiers $V'\_A$ and $V'\_B$ with new certificates $y'$ and $z'$:

$V'\_A(x,y'):$

1. $y'=\langle 0,\overline{x},\overline{y}\rangle$: If $f(x)\ne f(\overline{x})$, reject. Otherwise output $V\_A(\overline{x},\overline{y})$.
2. $y'=\langle 1,z\rangle$: Output $V\_B(f(x),z)$.

$V'\_B(x',z'):$

1. $z'=\langle 0,z\rangle$: Output $V\_B(x',z)$.
2. $z'=\langle 1,x,y\rangle$: If $x'\ne f(x)$, reject. Otherwise output $V\_A(x,y)$.

The polynomial-time computable functions $g$ and $h$ are defined as below:

$g(x,y')$

1. $y'=\langle 0,\overline{x},\overline{y}\rangle$: Output $\langle 1,\overline{x},\overline{y}\rangle$.
2. $y'=\langle 1,z\rangle$: Output $\langle 0,z\rangle$.

$h(x',z')$

1. $z'=\langle 0,z\rangle$: Output $\langle 1,z\rangle$.
2. $z'=\langle 1,x,y\rangle$: Output $\langle 0,x,y\rangle$.

Let $Y\_x$ be the set of all certificates of $x$ according to $V\_A$ and $Z\_{x'}$ be the set of all certificates of $x'$ according to $V\_B$. Then the set of all certificates of $x$ according to $V'\_A$ is $0\overline{x}Y\_\overline{x}+1Z\_{f(x)}$ such that $f(x)=f(\overline{x})$, and the set of all certificates of $x'$ according to $V'\_B$ is $0Z\_{x'}+1\overline{x}Y\_\overline{x}$ such that $x'=f(\overline{x})$.

(This is derived from the accepting language of $V'\_A$ and $V'\_B$.)

Now let $x'=f(x)$, the rest part is easy to check.

# Answer
> 14 votes
No. First note that Levin reduction only makes sense with respect to classes which certificate has a meaning, e.g. $\mathsf{NP}$ while Karp reduction is general. The word "certificate" for a problem makes sense only when a verifier is fixed. Levin's reduction assumes that the verifiers are fixed. You cannot change the verifiers. (In the following I assume that certificate verifiers are fixed as required by definition of Levin reduction.)

Second, Levin reduction means that one can find the certificate for one from the certificate for the other. It is true that the well-known Karp reductions between natural problems turn out to be Levin reduction but this does not need to be true in general.

If we can reduce instances of a problem $A$ to problem $B$ it doesn't mean we have a way of computing a certificate for one from a certificate for the other.

For this to be true we need the fact that a certificate search problem corresponding to the decision problem is polynomial time reducible to the decision problem. This is true for $\mathsf{NP\text{-}complete}$ problems but not known to be true generally even for $\mathsf{NP}$ problems.

# Answer
> 5 votes
A quick counterexample for your proof: suppose that $x\_1, x\_2 \in L\_1$, $f(x\_1) = f(x\_2) \in L\_2$, and $w$ is a valid certificate for $x\_1$ but not for $x\_2$

$M\_1'(x\_1,\langle 0,w \rangle)= M\_1(x\_1,w)=1$

$M\_1'(x\_2,\langle 0,w \rangle)= M\_1(x\_2,w)=0$

By definition $g(x\_1,\langle 0,w \rangle) = \langle 1,x\_1,w \rangle$

$f(x\_1)=f(x\_2)$ so $M'\_2(f(x\_2),\langle 1,x\_1, w \rangle)) = M\_1(x\_1,w) = 1$ so $\langle 1,x\_1, w \rangle$ is a valid certificate for $f(x\_2)$ but

$h(f(x\_2), \langle 1,x\_1, w \rangle) = \langle 0, w \rangle$ which is not a valid certificate for $x\_2$

---
Tags: complexity-theory, reductions, check-my-proof
---


# Question
Title: Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$?
Let $\mathbb F\in\\{\mathbb R, \mathbb C\\}$ the field of real or complex numbers. Then \[1, page 22 in the middle\] claims that the following equation can easily be solved in deterministic polynomial time: $$ \sum\_{i=1}^n a\_ix\_i^2=b$$ with $a\_i, b\in\mathbb F$. Some discussion suggests, that the algorithmical model assumed in the paper is that of a machine that can perform field operations in one step.

My question is: What is the algorithm? Is it multidimensional Newton? That would be weird because this algorithm only converges (in some cases) and does not give an exact solution. I'm quite unused to computational models over fields like the reals or complex numbers and maybe for someone who is more experienced this is cristal-clear?

\[1\] Agrawal & Saxena, On the complexity of cubic forms, 2006.

# Answer
> 6 votes
We assume that we are allowed to take square roots in $\mathbb{F}$.

$\mathbb{F} = \mathbb{C}$: If $b = 0$ then $x\_1 = \cdots = x\_n = 0$ is a solution. If $b \neq 0$ and $a\_1 = \cdots = a\_n = 0$ then there is no solution. Otherwise, let $a\_i \neq 0$, and then a solution is $x\_i = \sqrt{b/a\_i}$ and $x\_j = 0$ for $j \neq i$.

$\mathbb{F} = \mathbb{R}$: If $b = 0$ then $x\_1 = \cdots = x\_n = 0$ is a solution. Otherwise, without loss of generality assume that $b \> 0$ (otherwise, multiply all of $b,a\_1,\ldots,a\_n$ by $-1$). If $a\_i \leq 0$ for all $i$ there is no solution. Otherwise, let $a\_i \> 0$, and then a solution is $x\_i = \sqrt{b/a\_i}$ and $x\_j = 0$ for $j \neq i$.

---
Tags: algorithms, real-numbers
---


title: Is finding dead-end nodes in NL?

text:
# Question
Title: Is finding dead-end nodes in NL?
Given a directed graph $G$ and two nodes $s,t$, decide whether there is some node $s'$ such that $s'$ is reachable from $s$ while $t$ is *not* reachable from $s'$.

I am wondering whether this problem is in NL.

# Answer
It is in NL. Here is the outline of a possible proof:

* If you already fix *s*′, you can check whether *s*′ satisfies your condition or not in NL. Reachability is easy, non-reachability is by the Immerman–Szelepcsényi theorem, and taking the AND of two conditions is easy.
* Because there are only polynomially many possibilities for *s*′, you can test these possibilities one by one until you find the right *s*′ or find out that no such *s*′ exists. Alternatively, you can guess *s*′ by using nondeterminism.
> 9 votes

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


title: Are regular expressions $LR(k)$?

text:
# Question
Title: Are regular expressions $LR(k)$?
If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I know if a type 3 grammar is $LR(1)$, $LL(1)$, $SLR(1)$, etc. without constructing any parse tables?

# Answer
> 16 votes
All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token. Consequently, all regular languages are also LR(1), since any LL(1) grammar is LR(1). Additionally, using an important result from this paper, you can show that any LR(1) language has an SLR(1) grammar, meaning that any regular language has an SLR(1) grammar.

However, the regular languages are *not* all LR(0). The LR(0) languages have very specific properties - in particular, they must be prefix-free. Thus the regular language {a, aa} is not LR(0), though it's clearly regular (regex a|(aa)). However, the LR(0) languages are not properly contained within the regular languages; this grammar for { 0n21n | n ≥ 1 } is LR(0), but the language is not regular:

```
S -> E
E -> 0E1 | 2

```

Hope this helps!

# Answer
> 2 votes
(Plain old) regular expression *syntax* (you said "representation") is LR(0). You don't need any lookahead to parse a string representing a regex. You can easily decide this by running a parser generator on a grammar for regexes :-} You can also easily code a simple recursive descent (LL(0)) parser for regexps; anything which is LL(0) is LR(0).

I don't know if the syntax of more complicated so-called "regexps" such as Perl's are like this; but Perl's regexps are strictly more powerful than regexps so they are not plain old regexps.

To determine if a grammar has some property, you have to run some kind of predicate. To determine if it is (S)LR(k), you have to run a predicate that can check for that property. In effect, any such predicate must in effect build the parse tables, because of the way they are defined.

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


# Question
Title: Left recursion and left factoring -- which one goes first?
if I have a grammar having a production that contains both left recursion and left factoring like

$\qquad \displaystyle F \to FBa \mid cDS \mid c$

which one has priority, left recursion or left factoring?

# Answer
Transformations such as left factoring or removing left recursion do not have precedence rules. Obviously, the resulting grammars may be different but they will recognize the same language.

The question's example grammar is more difficult than the typical undergrad homework problem. So showing our work will be useful.

### Left Recursion

Let's define a transformation that removes left recursion.

Given

$\qquad \displaystyle A \to A\alpha\_0 \mid A \alpha\_1 \mid \dots \mid A \alpha\_n \mid B \beta\_0 \mid B \beta\_1 \mid \dots \mid B\beta\_n$,

we remove left recursion like this:

$\qquad \displaystyle \begin{align} A\_h &\to B \beta\_0 \mid B \beta\_1 \mid \dots \mid B \beta\_n \\ A\_t &\to \alpha\_0 \mid \alpha\_1 \mid \dots \mid \alpha\_n \\ A\_{t^+} &\to A\_t A\_{t^+} \mid A\_t \\ A &\to A\_h A\_{t^+} \mid A\_h \end{align}$

The generality of above is typically not given in compiler texts, but parsing texts like Grune & Jacobs do cover this. Left factoring can be applied to the above transformed grammar but will be just introduce extra rules that will not change the answer. So we will *simplify* the presentation without extra left factoring being performed.

In this answer we will not cover indirect left recursion issues because we are only concerned with a single non-terminal's rules. Note that indirect left recursion can be dealt with, though. (Open a separate question if that is important.)

### Left Factoring

Removing left factoring is in most introductory compiler texts done like this. Given

$\qquad \displaystyle A \to x y \mid x z$

left factoring yields:

$\qquad \displaystyle \begin{align} A\_s &\to y \mid z \\ A &\to x A\_s \end{align}$

Now that's perform the transformations in both ordering.

### Left factoring first

Let's left factor the question's grammar

$\qquad \displaystyle \begin{align} F\_s &\to D S \mid \varepsilon \\ F &\to F B a \mid c F\_s \end{align}$

and then remove the left recursion:

$\qquad \displaystyle \begin{align} F\_h &\to c F\_s \\ F\_t &\to B a \\ F\_{t^+} &\to F\_t F\_{t^+} | F\_t \\ F\_s &\to D S \mid \varepsilon \\ F &\to F\_h F\_{t^+} \mid F\_h \end{align}$

### Removing left-recursion first

And for the other ordering, let's remove left recursion from the question's grammar

$\qquad \displaystyle \begin{align} F\_h &\to c D S \mid c \\ F\_t &\to B a \\ F\_{t^+} &\to F\_t F\_{t^+} \mid F\_t \\ F &\to F\_h F\_{t^+} \mid F\_h \end{align}$

and then left factor the terminal $c$:

$\qquad \displaystyle \begin{align} F\_{hs} &\to D S \mid \varepsilon \\ F\_h &\to c F\_{hs} \\ F\_t &\to B a \\ F\_{t^+} &\to F\_t F\_{t^+} \mid F\_t \\ F &\to F\_h F\_{t^+} \mid F\_h \end{align}$

Aha, the resulting grammars are the same!

In general, proving that two grammars are equivalent is undecidable. So if a series grammar transformations could influence the *language that is recognized* then, it would be disastrous.
> 14 votes

---
Tags: formal-languages, formal-grammars, parsers, left-recursion
---


title: Does $NP^{NP}=NP$?

text:
# Question
Title: Does $NP^{NP}=NP$?
Is $NP$ with oracle access to $NP$ larger than just $NP$? As I understand $NP^ {NP}$ is just a turing machine that can make queries to an other $NP$ machine if so than $NP$ can simulate $NP^{NP}$? Is there something wrong with this argument?

# Answer
> 15 votes
To reformulate my comments as an answer, and to expand a bit:

We don't know whether **NPNP** = **NP** — it's a notoriously open problem in complexity theory, though as with **P** versus **NP** we suspect that they are not equal. One of the reasons why we don't know how to simulate an **NP** oracle with an **NP** machine is that we don't know how the **NP** machine could detect "no" instances of problems submitted to the oracle.

The class **NPNP** is also known as $\Sigma\_2^P$, and is *one of* the classes at the second level of the polynomial hierarchy. The other classes at the second level are $$\begin{align\*} \Delta\_2^P &:= \mathsf{P}^{\mathsf{NP}}, \\ \Pi\_2^P &:= \mathsf{coNP}^{\mathsf{NP}}. \end{align\*}$$ (All these classes would be the same if we used a **coNP** oracle; the only difference is in essence a logical negation of the output.) The classes of the third and higher levels of the hierarchy are defined by giving them yet further **NP** oracles: $$\begin{align\*} \Delta\_{k+1}^P &:= \mathsf{P}^{\\,\Sigma\_{k}^P} = \mathsf{P}^{\\,\Pi\_k^P}, \\\\[1ex\] \Sigma\_{k+1}^P &:= \mathsf{NP}^{\\,\Sigma\_{k}^P} = \mathsf{NP}^{\\,\Pi\_k^P}, \\\\[1ex\] \Pi\_{k+1}^P &:= \mathsf{coNP}^{\\,\Sigma\_{k}^P} = \mathsf{coNP}^{\\,\Pi\_k^P}. \\\end{align\*}$$ Again, the difference between the $\Sigma\_k^P$ and $\Pi\_k^P$ oracles is essentially negation of its output. We also define $\Delta\_0^P = \Sigma\_0^P = \Pi\_0^P = \mathsf{P}$; using the definition above, you can see that this gives us $\Delta\_1^P := \mathsf{P}$, $\Sigma\_1^P := \mathsf{NP}$, and $\Pi\_1^P := \mathsf{coNP}$.

The various classes of the polynomial hierarchy are thought to be distinct; that is, no matter how many layers of **NP** oracles you provide, the computational power is not thought to stabilize at any point. If **NPNP** = **NP**, then the polynomial hierarchy collapses to it's first level: all of the $\Sigma\_k^P$ classes for *k* ≥ 1 would be equal to **NP** (as would, for that matter, all of the $\Pi\_k^P$ classes including **coNP**, as an **NP** machine could solve any problem in $\Pi\_k^P$ by simulating some tower of **NP** oracles).

# Answer
> 6 votes
$\mathsf{NP}^{\mathsf{NP}}$ is known as the second level of polynomial hierarchy.

It is suspected that all levels of polynomial hierarchy are different. A machine with NP oracle can query it and negate the answer, therefore $\mathsf{NP}^{\mathsf{NP}} \supseteq \mathsf{coNP}$, while $\mathsf{NP} \supseteq \mathsf{coNP}$ seems unlikely.

---
Tags: complexity-theory
---


# Question
Title: How would a neural network deal with an arbitrary length output?
I've been looking into Recurrent Neural Networks, but I don't understand what the architecture of a neural network would look like when the output length is not necessarily fixed.

It seems like most networks I've read descriptions of require the output length to be equal to the input length or at least a fixed size. But how would you do something like convert a word to the string of corresponding phonemes?

The string of phonemes might be longer or shorter than the original word. I know you could sequence in the input characters using 8 input nodes (bitcode of the character) in a recurrent network, provided there's a loop in the network, but is this a common pattern for the output stream as well? Can you let the network provide provide something like a 'stop codon'?

I suppose a lot of practical networks, like those that do speech synthesis should have an output that is not fixed in length. How do people deal with that?

# Answer
You just add more neurons. You're right that it's often not useful (if you only get 5 bits of information in, it's hard to put 10 bits of information out), but if you want to (e.g. because your output format is less dense), go ahead.

As a trivial example, if you wanted to create an ANN to convert characters to graphemes (as represented on an 8x8 grid of on/off pixels) you could have 26 input neurons and 64 output neurons. Connect each input neuron to the output neurons which would be turned on if that character is being displayed; then the output neurons' function is just logical OR.

The standard learning algorithms like gradient descent should work fine no matter the size of the output layer.

---

EDIT: I guess your question is: "how do you handle *unknown* input and output lengths?" Any Turing machine can be simulated by a recurrent neural network, so you will never run into a "halting problem" (if I understand what you mean by that phrase).

It's very rare that you can't bound the size of the output as a function of the input size. So you just have some metalearning procedure which generates the network for you on the fly.

One common idea is that of "template" models. I'm not familiar with text-to-speech, but I guess you would make an assumption like "no phoneme spans more than 6 characters". So you build your network with 6 inputs, and just repeat it for as long as the word is. You need some rule like "each network gives the pronunciation of the middle two characters" to handle overlaps, as well as some special handling for the beginning and end of words too.
> 7 votes

---
Tags: neural-networks
---


# Question
Title: What is the difference between quantum TM and nondetermistic TM?
I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and *nondetermistic* TM are one and the same. The answers to the other question do not touch on that. Are these two models one and the same?

If no,

1. What are the differences between quantum TM and NDTM?
2. Is there any computation which a NDTM would do quicker than Quantum TM?
3. If this is the case then quantum TM is a DTM, then why is there so much fuzz about this technology, we already have so many DTM. Why to design a new DTM in the end?

# Answer
> 23 votes
As a general preamble, QTMs, TMs and NTMs are all different things (taking huge liberties with a bunch of unspoken assumptions).

I'll assume you know what a Turing Machine is.

1. A NTM is a TM where, at any state, with any symbol, the transition function is allowed to have a number of choices of action that is not precisely $1$, *i.e.* $0$ or more than $1$ (a deterministic TM must have exactly one action for each symbol at each state, though the $0$ case is easy to deal with). When faced with a situation where there are several choices of transition a NTM will make the choice that will ultimately take it to an accepting state, if such an option exists.
In contrast a QTM is a model of *quantum* computation, as detailed in the thread you linked. It is *not* nondeterministic, not all. Probably the key high level differences between a QTM and a TM is that a QTM has as its state a linear combination of the basis states (again, it's all in that other thread) and that it's probabilistic, that is, the accuracy of its ouput is bounded by some probability less than $1$ (broadly speaking).
Just to be really really clear on a point that catches many people, nondeterminism is not randomness, it's not parallelism, it's a theoretical construct that has nothing to do with either of those.
2. The full answer to this depends on some complexity theoretic assumptions. Taking a particular standpoint (that $QMA \supset BQP$ and $NP \supset P$), the answer is yes. $NP$-complete problems can be solved by a NTM in polynomial time, and it also seems that $NP\text{-complete} \cap BQP = \emptyset$, so they can't be solved by a QTM in polynomial time.
Again, this is all dependent on which way the cards fall with a variety of complexity classes. If it turns out that $QMA = BQP$ then the answer is no, for example.
3. The first thing to say here is to be careful about confusing TMs (of any kind) and computers. A TM is not a computer, a QTM is not a quantum computer. TMs (of any kind) model computation. What a given computer can do is governed by this, but this is quite different to saying that the thing I'm typing this on is a TM.
Having said that, if we speak loosely and lazily identify QTMs with quantum computers and TMs with standard computers, then (again under certain complexity assumptions) it seems that quantum computers can quickly do certain tasks that seem hard for standard computers (factoring, discrete logs, a really particular type of searching, and a couple of others). However these problems aren't known to be hard in the $NP$-complete sense either, it seems quantum computers offer capabilities that extend a standard computer, but in a different direction to what would be needed to solve $NP$-complete problems quickly.

Again just to be really clear, I've glossed over a lot of computational complexity here, if you really want to understand how everything fits together, you'll need start digging in to the literature.

# Answer
> 15 votes
### On the meaning of nondeterminism

There are two different meanings of 'nondeterminism' at issue here. Quantum mechanics is usually described as being "not deterministic", but the word "nondeterministic" is used in a specialized way in theoretical computer science.

1. One meaning, which applies to quantum mechanics, is just 'not deterministic'. This is usually a reasonable way to interpret the word, and in point of fact, neither quantum Turing machines nor even probabilistic Turing machines are deterministic in the way that they solve decision problems.
2. However, when describing models of computation, *nondeterministic* is used specifically to mean that the machine can (in a sense) make choices which are not determined by its state or its input, to obtain a particular objective. This meaning is used elsewhere in describing models of computation, such as Nondeterministic Finite Automata.

So, quantum Turing machines are a model of computation which is not deterministic, but which is different from a "**nondeterministic Turing machine**".

### Nondeterministic Turing Machines

A nondeterministic Turing machine is a machine which may explore multiple possible transitions. The transition that it makes at a given step depends, but is not determined, by the state that it is in and the symbol that it is reading. There are two ways this is commonly presented:

* Especially for the purposes of defining the complexity class **NP**, one may describe the machine as making choices (or guesses) at each step in order to *try to reach* an accepting state. If you think of what the nondeterministic machine is doing as exploring a decision tree, it is searching for an accepting path in the tree. While no mechanism which is described to suggest how such a path should be found, we imagine that it will find an accepting path if even just one exists.
* It is also quite common to say that a nondeterministic machine explores all possible paths in the decision tree in parallel, and gives a "yes" answer if *any* of them turn out to be an accepting path.

More modern treatments of nondeterminism also consider not just the existence, but the *number* of accepting paths; and this is well-suited to the description of exploring all paths in parallel. We can impose extra constraints, for instance that all computational paths have the same length (that the machine always takes the same amount of time to perform a computation) and that each path performs a guess at each step, or every second step, even if the guess is not used. If we do this, we can formulate probabilistic models of computation, such as random Turing machines (motivating complexity classes such as **BPP**), in terms of the *number* of accepting paths of a nondeterministic Turing machine. We can also turn this around, and describe nondeterministic Turing machines in terms of randomized computers which can somehow distinguish between outcomes which have *zero* probability from ones which have *non-zero* probability.

### Quantum Turing machines

The main difference between a quantum Turing machine and a nondeterministic one is this: instead of nondeterministically 'choosing' a single transition out of two or more at each step, a quantum Turing machine makes a transition to a superposition of one or more possible transitions. The complete state of the machine is defined as a unit vector in a complex vector space, defined by linear combinations of basis states described by classical states of the tape, the position of the machine head, and the "internal state" of the machine head. (See *e.g.* page 9, Definition 3.2.2, of *Quantum Complexity Theory* for the complete description of how quantum Turing machines make transitions.) The condition under which the quantum Turing machine accepts an input is also more restrictive, and inherently involves probability, requiring a substantial probability of observing the correct outcome in order to succeed.

As a result, quantum Turing machines differ from nondeterministic machines in that the way they make their transitions are not completely unspecified. Even if the transition "seems mysterious", it's also the same sorts of evolution with time that our best theory of matter indicates happens in the real world. While it is common to describe quantum computers as "exploring different computational paths in parallel", it's not particularly useful to do: the amplitudes on the different paths mean that they don't all have the same importance, and unlike nondeterministic Turing machines, it isn't enough to have non-zero amplitude on some outcome; it has to be possible to obtain a very large probability of obtaining the correct outcome, such as 2/3. (The class of problems **BQP** which a quantum Turing machine can efficiently solve requires a probability gap of the same sort as **BPP** has for randomized computation.) Furthermore, very much in contrast to nondeterministic Turing machines, *a quantum Turing machine can interfere those with one another after they have split*, which is simply impossible in the typical formulation of a nondeterministic Turing machine (and it makes the description in terms of a decision tree less useful in the first place).

### Comparing the two models

We don't know whether one of these machines is more powerful than the other; the different ways in which they are not-deterministic seem different from one another, and hard to compare.

As for the problems that each machine can quickly do, that the other cannot (so far as we know):

* We don't know any way that a quantum Turing machine could quickly solve the SATISFIABILITY problem. A nondeterministic Turing machine can, easily.
* Work by Aaronson and Archipov (The Computational Complexity of Linear Optics) suggests that nondeterministic Turing machines are unlikely to be able to efficiently simulate certain experiments of linear optics which could be simulated by a quantum Turing machine.

But even if someone shows how to relate the two sorts of machine to one another — and even in the extremely unlikely scenario that someone shows that **BQP** = **NP** (the problems that a quantum Turing machine, and a nondeterministic Turing machine, can respectively solve quickly) — the two machines which define these models of computation are quite different from one another.

---
Tags: computability, turing-machines, quantum-computing, nondeterminism
---


title: Polygons generated by a set of segments

text:
# Question
Title: Polygons generated by a set of segments
Given a set of segments, I would like to compute the set of closed polygons inside the convex hull of the set of the end of those segments. The vertices of the polygons are the intersections of the segments. For example, if you draw the 6 lines restricted which equations are: $x=-1$, $x=0$, $x=1$, $y=-1$, $y=0$, $y=1$, I would like the algorithm to output the four unit squares around the origin.

# Answer
> 9 votes
You're trying to compute something called the **arrangement** of the line segments. The arrangement is a planar straight-line graph whose vertices are either endpoints or intersection points of line segments. The vertices partition the lines segments into smaller segments, which are the edges of the arrangement. Finally, the vertices and edges partition the plane into several components; these are the faces of the arrangement.

Suppose you are given $n$ line segments, and $k$ pairs of those line segments intersect. (You don't know $k$ in advance.) The intersection points can be computed in $O((n+k)\log n)$ time using the Bentley-Ottmann sweep-line algorithm. (The running time can be reduced to $O(n\log n + I)$ using a more complicated algorithm, where $I\le k$ is the number of intersection points, but the additional effort is probably not worth it.) The algorithm can be modified to report, for each intersection point, which segments intersect at that point. Then it is simply a matter of careful bookkeeping to construct a standard data structure that represents the arrangement.

A few caveats to keep in mind:

* The faces of the arrangement are not necessarily simple polygons. If the union of the line segments is connected, each *bounded* face is a weakly simple polygon, but a single edge can be incident to the face no both sides. If the union of the segments is disconnected, then faces can have holes, which are either trees or weakly simple polygons.
* Most textbook (and Wikipedia) descriptions of the Bentley-Ottmann algorithm assume that the input segments are in general position. In this context, "general position" means that at most two segments intersect at any point; no segment endpoint lies on another segment (in particular, the intersection of two segments is either empty or a single point); and no two endpoints have the same $x$-coordinate. In practice, however, this assumption does not hold. As usual in computational geometry, handling degenerate cases correctly and robustly is the most difficult part of implementing the algorithm. (What does your implementation do when the input contains 42 copies of the segment \[(0,0),(1,1)\], 17 copies of the segment \[(0,0),(2,2)\], and 9 copies of the zero-length segment \[(1,1),(1,1)\]?)
* For small numbers of segments (at most a few dozen), it's probably faster to use a brute-force $O(n^2)$-time algorithm to compute the intersection points.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Context-free grammar to a pushdown automaton
I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have on a homework that's due later today, so I'd appreciate some kind of help, even if it's just an explanation of the correct answers diagram. I need a PDA corresponding to this CFG:

$$S \rightarrow aSa | bSb | B$$ $$B \rightarrow bB | \epsilon$$

I know it will have to push X every time 'a' is read before a 'b', and pop X every time 'a' is read after a 'b'. But I'm not sure how to arrange the PDA in order to tell which a's came after b's. Also, I'm unsure of how to deal with the b's in terms of the stack, as there can be as many in the middle of the string as you want. Help appreciated.

Thanks, Pachun

# Answer
This is basically the language of all palindromes over $\\{a, b\\}$ which can contain an arbitrary number of $b$'s in the middle. First, you could build a PDA for palindromes. This is a fairly standard language, so you should be able to find plenty to get you started. Then, you need to add a way to read an arbitrary number of $b$'s after you're done pushing new symbols to the stack, and before you start popping symbols. So the basic steps here:

1. Read $a$'s and $b$'s and push to the stack;
2. Read any number of $b$'s;
3. Read $a$'s and $b$'s and pop from the stack.

Please let me know if you need more guidance. Note that you're going to need to use nondeterminism here, so don't worry about it. This is a not a deterministic language (unless I'm mistaken... which has happened before).
> 2 votes

---
Tags: formal-grammars, context-free, pushdown-automata
---


# Question
Title: Algorithm to translate a deterministic Büchi automaton to LTL (when possible)
Linear temporal logic and deterministic Büchi automata are incomparable: DBA cannot express $FGa$, and LTL cannot express *"at least each odd letter is 'a'"*. But sometimes it is interesting to know whether the language of a DBA can be expressed in LTL.

I need an algorithm that decides whether a language of a given DBA is describable in LTL. Do you know algorithms for that?

# Answer
> 5 votes
You may find the algorithm in Diekert and Gastin's paper, Section 12. It works for both NBW and DBW (provided that you have the $\omega$-expression), and this can be decided in polynomial time.

---
Tags: logic, automata, linear-temporal-logic, buchi-automata
---


# Question
Title: What complexity class does this variation of traveling salesman problem belong to?
Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers.

The problem is in PSPACE but even the verification problem seems to be NP-hard. Is that true?

If the verification problem is NP-hard, what exact complexity class does this problem belong to?

# Answer
> 10 votes
I'm assuming that you're thinking of the *Euclidean* traveling salesman problem, where $c$ and $v$ are vectors in $\mathbb{Z}^{2n}$, with two coordinates for each city. Let $minTSP(c)$ denote the length of the minimum traveling salesman tour for the cities with coordinates $c$. Then your problem asks whether $$ minTSP(c + v) \ge min TSP(c) + x. $$ But then the special case $c=0$ is equivalent to asking whether $minTSP(v) \ge x$, which is **coNP-hard**.

---
Tags: complexity-theory, reductions, np-hard, decision-problem, traveling-salesman
---


title: Function Maximization in Java

text:
# Question
Title: Function Maximization in Java
I have a bivariate function like

$ f(x,y) = \frac{1}{x^3 \sqrt{\pi}}. e^{\frac{2-x}{x^2}} . y^3 . e^{3.y \over 3-y} $

and I want to find its global maximum over a range of $ x \in \[0, 200\] \text{, and } y \in \[300,50000\] $

What kind of algorithms I can use to find the global maximum. I want to have keywords for searching and finding materials.

Are there any java library which I can use to solve these kind of problems?

# Answer
> 4 votes
The most basic algorithm is probably gradient gescent which can also be used for maximization. It uses the gradient of the function to optimize and (starting from an initial point) "goes" into the most promising direction. For maximization this is the direction of the gradient. Look at the examples on Wikipedia. That should give you an idea how it works. Note that in is pure variant, it always gets stuck in local optima. I don't know if there is a Java library for this. I programmed it myself some time ago, but this code is very specific to the task.

Another thing to look at is the Nelder-Mead method. It is also susceptible to local minima and requires a smooth function. It is implemented in Flanagan's Java Scientific Library. Basically you have to extend `MaximizationFunction` and implement the function

```
public double function(double[] param)

```

which contains your function above. This method evaluates your function given the parameters `param` (in your case two values: `x` and `y`) and returns the function value.

Then you can use the whole program like this:

```
//Create instance of Maximisation
Maximization max = new Maximization();

// Create instace of class holding function to be maximised
YourFunction funct = new YourFunction();

// initial estimates (your initial x and y)
double[] start = {100.0, 3000.0};

// initial step sizes (take a good guess)
double[] step = new double[start.length];
Arrays.fill(step, 100);

// convergence tolerance
double ftol = 0.0001;

// maximal number of iterations
int maxIter = 5000;

// Nelder and Mead maximisation procedure
max.nelderMead(funct, start, step, ftol, maxIter);

// result of maximization
double result = max.getMaximum()

```

Since your variables have restrictions, you should add some constraints via the `addConstraint` method of `Maximization`.

# Answer
> 0 votes
You can try using a optimization algorithm like Particle Swarm Optimization or Genetic Algorithms. Matlab has a professional toolbox for GA and there are many written in Java.

Or you can try using this: https://github.com/madflame991/gloptat. (It's in Java) (Function optimization like this was the topic of my bachelor's thesis)

---
Tags: algorithms, optimization, mathematical-analysis, mathematical-software
---


title: Building a finite state transducer

text:
# Question
Title: Building a finite state transducer
I know it's possible to build a Finite State Transducer for converting numbers from base 2 to base 4 or 8 or other powers of 2 (translating from base N to base N^M is easy). However I've never seen a FST that can convert numbers from base 1 to base 2 or viceversa. Can a FST even do this? If so, can you please give some hints on building such a FST?

# Answer
In my opinion, such transducers does not exist.

It is not possible to convert from base 2 to base 1, since the regular language $\\{10^n\ |\ n \in \mathbb{N}\\}$ would become $\\{1^{2^n}\ |\ n \in \mathbb{N}\\}$, which is nonregular. However, regular languages are closed under the translation by the finite state transducer.

On the other hand, I was not able to find such a straightforward proof for the opposite case (that does not mean that such a proof does not exist). But I am inclined to believe that it is not possible as well. The reason is that the transducer would have some transitions writing $\varepsilon$ and some transitions writing non-$\varepsilon$ words. However, since the length of the image of $w, |w| = n$ is $O(\log n)$, the transitions writing non-$\varepsilon$ words are used significantly less (but nonconstant number of times) than the $\varepsilon$-transitions *on all inputs.* However, for a finite state transducer, a transition is either used a constant number of times, or there exists an input such that the number of uses of that transition is at least $\frac{1}{m} n$, where $m$ is number of transitions and $n$ is the length of the input (this is not so hard to prove). Moreover, clearly, such input exists for arbitrarily large $n$. Therefore, we get a contradiction.
> 5 votes

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


title: LTS of this simple FSP

text:
# Question
Title: LTS of this simple FSP
I have this finite-state process with the corresponding labeled transition system:

The FSP is:

```
MAKER = (kochen -> fertig -> MAKER).
USER = (fertig -> essen -> USER).

||MAKER_USER = (USER||MAKER).

```

Why is `essen` possible after the second `kochen`? `USER` needs to have `fertig` in order to able to `essen` right?

# Answer
The middle transition `fertig` is the shared action so this must be ran parallel, but after this there are 2 transitions which dont have to run parallel, one is `kochen` and the other is `essen`.

Assume, we are now in the point where `fertig` is done by both processes and now we have 2 options, `kochen` and `essen`. We do both one after another as options: if i do `kochen` then the option `essen` is left, if i do `essen`, then `kochen` is left. I also have to do what is left to do.

So, let's say, I choose `essen` then go to `USER` back, but if I do `kochen` first, then I have to do `essen` which is the second `essen` in this case.
> 1 votes

---
Tags: automata, finite-automata, process-algebras
---


# Question
Title: Minimize the maximum component of a sum of vectors
I'd like to learn something about this optimization problem: For given non-negative whole numbers $a\_{i,j,k}$, find a function $f$ minimizing the expression

$$\max\_k \sum\_i a\_{i,f(i),k}$$

An example using a different formulation might make it clearer: You're given a set of sets of vectors like

```
{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

```

Choose one vector from each set, so that the maximum component of their sum is minimal. For example, you may choose

```
(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

```

with the maximum component equal to 2, which is clearly optimal here.

I'm curious if this is a well-known problem and what problem-specific approximate solution methods are available. It should be fast and easy to program (no ILP solver, etc.). No exact solution is needed as it's only an approximation of the real problem.

---

I see that I should have added some details about the problem instances I'm interested in:

* $i \in \\{0, 1, \ldots, 63\\}$, i.e., there're always 64 rows (when written as in the above example).
* $j \in \\{0, 1\\}$, i.e., there're only 2 vectors per row.
* $k \in \\{0, 1, \ldots, N-1\\}$ where $N$ (the vector length) is between 10 and 1000.

Moreover, on each row the sum of the elements of all vectors is the same, i.e.,

$$\forall i, j, j':\quad \sum\_k a\_{i,j,k} = \sum\_k a\_{i,j',k}$$

and the sum of the elements of the sum vector is less than its length, i.e.,

$$\sum\_k \sum\_i a\_{i,f(i),k} \< N$$

# Answer
Reduction from 3SAT to the two-vector version: given a formula, let $i$ index variables, $j \in \\{0,1\\}$, and $k$ index clauses. Let $a\_{i,j,k}$ be the number of times variable $i$ appears positively (if $j = 0$) or negatively (if $j = 1$) in clause $k$. OPT is less than $3$ iff the formula is satisfiable (the bijection is obvious).

How I would attack this problem: large neighborhood search. Start with any solution. Choose $r$ rows at random. Use brute force to find the best solution where $f$ can change only on those rows—very doable for even moderate $k$ given that the problem size is $64$ rows. Repeat.
> 7 votes

# Answer
We cannot discuss the complexity of a problem when the problem size is fixed to a constant, because (most part of) the complexity theory deals with the asymptotic behavior of the complexity of the problem as the problem size tends to infinity. Here, I consider both the number of rows and the dimention of the vectors as variables.

Then the problem is NP-complete even if the numbers in the input are given in unary. This is not an answer to your question because you are asking about approximation, but it is something.

Define the problem rigorously:

*Instance*: *n* pairs of vectors *a**i*, *b**i* ∈ ℕ*m* (*i* ∈ {1, …, *n*}), and *K* ∈ ℕ, all in unary.
*Question*: Can we choose either *a**i* or *b**i* for each *i* so that the sum of these *n* vectors has at most *K* in each coordinate?

The following is a known NP-complete problem called 3-partition:

**3-partition**
*Instance*: *B* ∈ ℕ, and 3*k* integers *c*1, …, *c*3*k* between *B*/4 and *B*/2, exclusive, such that ∑*i*=13*k* *c**i* = *kB*, all in unary.
*Question*: Can the multiset {*c*1, …, *c*3*k*} be partitioned into *k* multisets *S*1, …, *S**k* such that the sum of each *S**j* is equal to *B*?

Given an instance (*B*; *c*1, …, *c*3*k*) of the 3-partition problem, construct an instance of the above problem as follows. For each *i* = 1, …, 3*k* and *j* = 1, …, *k*, we will construct a pair of 4*k*-dimensional vectors, representing the choice on whether *c**i* belongs to *S**j* or not:

* The vector representing the choice “*c**i**S**j*” has only one nonzero entry, which is (*k*−1)*c**i* at the *j*th coordinate.
* The vector representing the choice “*c**i**S**j*” also has only one nonzero entry, which is *B* at the (*k*+*i*)-th coordinate.

It is not hard to see that the instance (*B*; *c*1, …, *c*3*k*) of the 3-partition problem has a solution if and only if there is a way to choose a vector from each of the 3*k*2 constructed pairs so that all the coordinates of the sum of these vectors are at most (*k*−1)*B*. (In fact, when this happens, all the coordinates of the sum are equal to (*k*−1)*B*.) So this is a reduction from the 3-partition problem to the above problem.

So far, I ignored the two additional constraints stated at the end of the question, but both are easy to enforce by modifying this reduction slightly. The condition that the sum of the elements of each vector is equal can be enforced by appending dummy coordinates which contain only 0 or 1. The condition that this sum is less than the dimension can be enforced by appending dummy coordinates which contain only 0.
> 7 votes

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


# Question
Title: Sub-linear-time ordered set (!= sorted set) implementation?
Does there exist any data structure that efficiently (linearithmic-or-similar in-order traversal, sublinear time insertion/search/removal) implements an ordered set (i.e. a set that allows for enumerating the items in insertion order)?

If so, what data structure is it/how does it do this?

# Answer
Another pretty simple solution is a balanced binary search tree with threading (an overlaid linked list passing through all the nodes of the tree in order of their original insertion). Then insertion/search/removal are all O(log n), and iteration is O(n). You just update insert/remove to either append to the linked list or remove the node from it.
> 4 votes

# Answer
Okay, I guess this is just a case of me being silly... thanks to the people who commented above who made me realize this.

I can just use a hashtable, and keep a counter along with the item.

To traverse in order of insertion? Just dump it into an array and sort it with respect to the counter.
Traversal is O(n) anyway, so O(n log n) sorting won't really make a difference.
> 0 votes

---
Tags: data-structures
---


# Question
Title: Time complexity version of the Church-Turing Thesis
There's a lot of debate about what exactly the Church-Turing thesis is, but roughly it's the argument that "undecidable" should be considered equivalent to "undecidable by a universal turing machine."

I'm wondering if there's an analogous statement for time complexity, i.e. an argument that if some language is decided in $\Theta\left(f(n)\right)$ on a universal turing machine, then we should say its time complexity is $\Theta\left(f(n)\right)$.

This isn't equivalent to the CT thesis - e.g. quantum computers decide precisely those languages which are decidable in a non-quantum TM, but they may run that decision procedure more quickly.

# Answer
> 7 votes
### Short answer

The thesis that *all reasonable models of computation are polynomially-equivalent* — that is, in the amount of work that they perform; whether sequentially or in parallel, albeit different by some polynomial scaling factor — is generally known as the *Strong Church-Turing thesis* or the *Extended Church-Turing Thesis.*

### Details

The idea that all reasonable models of computation are equivalent up to polynomial factors is most important to two groups of researchers:

* Those working in quantum computation (who most often believe that it is false, or at least that if it were true that it would have very important implications for physics), and
* Those who are specifically skeptical towards the feasibility of quantum computers (who believe that the thesis is true, typically because quantum computers are the only thing which has come close to a 'reasonable' model of computation, and because the feel that quantum computers would somehow requires access to an unreasonable amount of information to carry out computations).

I started doing a bit of a literature search starting from Sid's link to the *Computational Complexity* blog entry above. That blog entry specifically concerned the Strong Church Turing Thesis, and asked whether anyone actually cared about such an "extended" version of the Church-Turing thesis before quantum computing came along.

It turns out that people have been trying to formulate this notion for a while however. It would seem that at the very least, the Strong Church-Turing Thesis arose naturally from concerns about what "reasonable computational models" could or could not achieve, in the context of *sequential* versus *parallelized* computing. There is both a "sequential" and "parallelized" computational thesis, which concern how different either sequential or parallelized models of computing can be with respect to computational power. Here are some quotations showing some of the history of the sequential thesis, which would be the one which quantum computing would be most naturally construed to violate.

> The belief that all reasonable sequential computers which will ever be dreamed of have polynomially related execution times is called *the sequential computation thesis*.

— Goldschlager, Lister. *Computer science: a modern introduction.* Prentice/Hall International, 1982 (p. 96).

> \[The\] *sequential computation thesis* \[10\] states that time on all "reasonable" sequential machine models is related by a polynomial.

— Parberry, *Parallel speedup of sequential machines: a defense of parallel computation thesis.* ACM SIGACT News **18** (pp. 54-67), 1986.

> "Reasonable" machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

— van Emde Boas, *Machine Models and Simulations*. Handbook of Theoretical Computer Science **A**, Elsevier, 1990.

---
Tags: computability, terminology, turing-machines, church-turing-thesis
---


# Question
Title: Finding Feature Representation Such That Two Samples Are Similar in Feature Space
Consider one specific useful function of our human brain: abstraction of object. Take the example of two pictures: if we are told the pictures are similar, we actually make conclusion about the aspects in which they are close to each other.

I'm considering whether machine can have the ability described. More accurately, is it possible to find and select a set of feature representations of two samples (e.g. image, sound) such that under those representations, the samples are similar with respect to a metric, say weighted euclidean norm?

# Answer
> 4 votes
I think you're looking for metric learning or Manifold learning. At a very high level, the idea behind both of these approaches is to learn the space (or transform) over which a set of (labeled) examples are close to one another.

# Answer
> 2 votes
Did you have a look at principal component analysis? It's basically the simplest of an array of dimension-reducing methods. It does the following:

Given a set of data points with with dimension, say, $n$, it transforms them into data points with dimension $k\<n$, where $k$ is a parameter. The transformation is such that the first principal component has the highest variance in the data, the second one is orthogonal and has the 2nd-highest variance, and so on.

This intuitively gives you a vector which throws away all the information that is constant in the data, and filters out information that varies throughout your input. For instance, imagine you have 100 pictures of a hand from the same perspective. Then, after the PCA the first component might indicate the position of the thumb, the second one the space between index and middle finger, and so on.

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: Does a never-halting machine always loop?
A Turing machine that returns to a previously encountered state with its read/write head on the same cell of the exact same tape will be caught in a loop. Such a machine doesn't halt.

Can someone give an example of a never-halting machine that doesn't loop?

# Answer
Consider the TM that always moves the tape head to the right and prints a special non-blank tape symbol at each step. This means that the TM never halts, since it always moves to the right, and never repeats a state, since after k steps the tape head is over the kth cell of the machine. Consequently, each configuration of the machine is different from all others, and the machine always loops.

We could also nonconstructively show the existence of such machines. Assume for contradiction that every TM that never halts eventually loops. This means that if you start a TM $M$ on a string $w$, one of the following will eventually happen:

1. $M$ halts, or
2. $M$ repeats a configuration.

In this case, the halting problem would be decidable as follows. Given a TM $M$ and string $w$, simulate $M$ on $w$, at each point writing out the contents of the tape, current state, and current tape position. If this configuration is a duplicate, output "does not halt." Otherwise, if $M$ halts on $w$, output "halts." Since one of these is guaranteed to happen eventually, this process always terminates, so we would have an algorithm for the halting problem, which we know does not exist.

Hope this helps!
> 15 votes

# Answer
A Turing machine which computes all of the decimal places of π (or any other non-terminating fraction, in any base) never halts, and can be made to write on each cell only a finite number of times. Of course, the fact that there is no transition to a halting state would be a dead giveaway, but it is at least a natural example.

A more interesting (but also ambiguous) case would be a Turing machine which iteratively computes the Collatz function on its input, $$ f(n) = \begin{cases} 3n+1 , & \text{if $n$ is odd}; \\ n/2, & \text{if $n$ is even}, \end{cases} $$ terminating if and only if it obtains the integer 1. The famous *Collatz conjecture* is that for any input, this procedure eventually halts. But it is not known whether this is the case. It can fail in two different ways, in principle: either it can find a sequence of integers which loops around (corresponding to the existence of an integer *n* such that $f \circ f \circ \cdots f(n) = n$ for some number of compositions, where *n* ≠ 1); or it could be that there are chains of integers *n*, *f(n)*, *f(f(n))*, ... which asymptotically diverge to infinity. If any sequences of the latter sort exist, this would imply that the Turing machine I've described above would be non-repeating, as the tape would be continually changed to larger and larger numbers.
> 12 votes

# Answer
Consider any non-halting Turing machine that never moves the read/write head to the left.
> 10 votes

# Answer
If this were true, then the halting problem would be decidable. You would just record each (tape, state) pair seen when executing the Turing machine, and the machine would either halt (in which case it obviously halts), or you see a pair that you've seen before, in which case the machine does not halt.

Since the halting problem is undecidable, this cannot be true. (See other examples for counter examples.)
> 5 votes

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


# Question
Title: How to convert a non-embedding context free grammar to regular grammar?
A context-free grammar is said to be self-embedding if and only if contains a derivation of the form $\xi\stackrel\*\Rightarrow u\xi v$, where $\xi$ is a non-terminal and $u$, $v$ are some non-empty words.

Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given an input context-free grammar that is not self-embedding, is there any algorithm to convert it to regular grammar, or DFA directly?

# Answer
Check out this link. This is a simpler version of a proof by Chomsky that NSE grammars represent regular languages. Fortunately, the proof technique illustrates how to construct a left-regular grammar from a given NSE grammar. Here's my explanation:

1. For each of the $\lvert V \rvert (\lvert V \rvert +1)/2$ pairs $(v\_1, v\_2)$ of elements of $V$, decide whether $v\_1 \le v\_2$ based on the definition given: $v\_1 \le v\_2$ if $v\_2 \*:= V^\* v\_1 V^\*$.
2. Construct equivalence classes such that if $v\_1 \le v\_2$ and $v\_2 \le v\_1$, $v\_1$ and $v\_2$ are in the same equivalence class. This will be a partition of all elements of $V$ into one or more equivalence classes.
3. Now, for each pair $(VE\_1, VE\_2)$ of equivalence classes of $V$ as described above, determine whether $VE\_1 \le VE\_2$ by checking whether $v\_1$ in $VE\_1 \le v\_2$ in $VE\_2$.
4. Construct sets $UE$ corresponding to equivalence classes $VE$ such that if $VE\_i \le VE\_k$, $VE\_i$ is a subset of $UE\_k$. Each $UE\_k$ must also contain the alphabet set $E$. You will have one $UE$ for each $VE$, and each $UE$ will contain variables in equivalence classes "less than" the corresponding $VE$, in addition to all the alphabet symbols.
5. Determine $P(v)$ for each variable $v$ as follows: $P(v)$ is the set of all productions in $P$ whose left-hand-sides belong to the equivalence class containing variable $v$.
6. For each variable $v$, construct a grammar as follows: $G(v) = (VE \cup UE, UE, P(v), v)$, where $VE$ is the equivalence class containing $v$ and the $UE$ is the one corresponding to the $VE$.
7. The authors have proven a lemma which claims that $G(v)$ is a linear grammar. From this, we can write regular expressions over $UE$ for each variable $v$. Note that for the $UE$ corresponding to the "smallest" $VE$, this regular expression will contain only symbols from the original alphabet $E$.
8. Iteratively substitute regular expressions containing only alphabet symbols into more complicated regular expressions obtained from step 7. Eventually, you will have a regular expression corresponding to the language generated from the original start symbol $S$, and this regular expression will contain only alphabet symbols from the original alphabet.
9. You now have a regular expression for the NSE grammar, and can obtain a minimal DFA using Kleene's theorem, the subset construction, and a DFA minimization algorithm.

If you would like an example, I can try to provide one later. Try to do a few yourself, read the paper (it's short), and we can talk about complexity later on.
> 5 votes

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


# Question
Title: Canonical reference on agent-based computing
I am interested in exploring the world of BDI agents (software agents that possess "beliefs, desires, intentions", essentially the agent has knowledge of the world, a set of motivations, and carries out certain plans).

I recently read A Canonical Agent Model for Healthcare Applications \[1\], which left me with a lot of questions, particularly about the specialization of different agent models for particular applications.

The particular modeling language used in their examples was ProForma, and I understand that this is more for the abstract specification of an agent, and that something like 3APL can be used as an actual programming language in this regard, with syntax like:

```
BELIEFBASE {
    status(standby).
    at(0,0).
    location(r1,2,4).
    location(r5,6,1).
    dirty(r1).
    dirty(r5).
}

```

My question is, all of these systems clearly reflect years of cumulative efforts, and rather than jumping in to the deep end, I'd like to ease into this world of research a bit more slowly. Is there a canonical reference in this area that might be able to provide a more general overview of all of these levels of organization, and where the abstractions stop and the implementations begin?

---

1. Fox J., Glasspool, D., Modgil, S. A Canonical Agent Model for Healthcare Applications. *IEEE Intelligent Systems, 21*(6), 21-28, 2006.

# Answer
If you want to approach this field from a computer science perspective then the standard reference I would recommend is:

> Yoav Shoham and Kevin Leyton-Brown \[2009\], "Multiagent systems: algorithmic, game-theoretic, and logical foundations", Cambridge University press.

Currently, it seems like the focus of theoretical work in this field (and this is obviously biased by my own interests) is to consider environments where agents are limited in their interactions. If you just have agents meet randomly, then ABMs are usually overkill and things can be done analytically. However, if there is some interesting network structure (fixed or dynamic) to the interactions (as there often is in real life) then ABMs become an essential tool. A good book discussing some of these ideas from a CS perspective is:

> David Easley and Jon Kleinberg \[2010\], "Networks, crowds, and markets: Reasoning about a highly connected world," Cambridge University press. (draft available online)

### Questions of interest:
> 3 votes

---
Tags: reference-request, human-computing, agent-based-computing
---


# Question
Title: Determining how similar a given string is to a collection of strings
I'm not sure if this question belongs here and I apologize if not. What I am looking to do is to develop a programmatic way in which I can probabilistically determine whether a given string "belongs" in a bag of strings. For example, if I have bag of 10,000 US city names, and then I have the string "Philadelphia", I would like some quantitative measure of how likely 'Philadelphia' is a US city name based on the US city names I already know. While I know I won't be able to separate real city names from fake city names in this context, I would at least expect to have strings such as "123.75" and "The quick red fox jumped over the lazy brown dogs" excluded given some threshold.

To get started, I've looked at Levenshtein Distance and poked around a bit on how that's been applied to problems at least somewhat similar to the one I'm trying to solve. One interesting application I found was plagiarism detection, with one paper describing how Levenshtein distance was used with a modified Smith-Waterman algorithm to score papers based on how likely they were a plagarized version of a given base paper. My question is if anyone could point me in the right direction with other established algorithms or methodologies that might help me. I get the feeling that this may be a problem someone in the past has tried to solve but so far my Google-fu has failed me.

# Answer
> 5 votes
Some better statistics to think of are word length and $n$-gram analysis. For word length, you can collect statistics of the distribution of word length of city names, and compare it to the length of what you get. $n$-gram analysis looks at the distribution of sequences of $n$ letters in your sample text (say $n=2$). Both approaches can be combined.

Given the heuristics, you can use *likelihood* to get a score which would (hopefully) be higher for your sample data than for other text. In order to determine a reasonable threshold, you can perform cross-validation. Pick a set of sample phrases which are *not* city names. Divide the city names into two parts, a large (say 80%) part and a small (say 20%) part. Train your model on the large part (that is, collect statistics on the large part), and then evaluate your model on the small part and on the sample of bad phrases. Determine if there is a reasonable threshold that passes most city names, but only a small amount of bad phrases.

---
Tags: algorithms, reference-request, string-metrics
---


# Question
Title: Kolmogorov complexity of a decision problem
What's the definition of Kolmogorov complexity for a decision problem? For example, how to define the length of the shortest program that solves the 3SAT problem? Is it the "smallest" Turing machine that recognizes the 3SAT langauge?

# Answer
> 4 votes
We can view of a language $A$ as an infinite binary string (the infinite binary string corresponding to the characteristic function of $A$) and then use the notion of Kolmogorov complexity for such strings.

Google for: Kolmogorov complexity infinite words

# Answer
> 4 votes
Like Kaveh said, you can view a decision problem as a language consisting of the descriptions of all the "yes" instances. Then the Kolmogorov complexity of the language is, as you said, the length of the smallest program that produces all those descriptions.

How we describe the program that generates the instances (and hence defines the Kolmogorov complexity) is in a sense a matter of agreement. To do it we first pick a universal description language which we will use describe all languages. Exactly what this universal language is however is somehow not that interesting. Turing Machines are a possible choice, however the Kolmogorov complexity of a string is in general incomputable, so the precise encoding language is less interesting than the more general implications that are true for any reasonable encoding.

---
Tags: computability, terminology, decision-problem, kolmogorov-complexity, 3-sat
---


# Question
Title: An $\mathbb F$-algebra as input to an algorithm
I want to specify, what it means to give an algebra as input to an algorithm and didn't find very much literature about it. So first I want to ask if you can recommend a book or paper that deals with the topic of complexity analysis of algebras over fields *and clearly define the decision problem*.

After some digging I found *something* and want to share it here and furthermore ask if the definitions make sense and are in compliance with literature (if there is any):

> **Definition:** Let $\mathbb F$ be a field and $A$ be a finitely generated commutative $\mathbb F$-algebra with additive basis $b\_1,\ldots, b\_n\in\mathbb F$. We now want to capture the multiplicative structure of the algebra and therefore write every product of base elements as a linear combination of all base elements: $$ \forall 1\leq i, j, k\leq n: \exists a\_{ijk}: b\_ib\_j=\sum\_{k=1}^n a\_{ijk}b\_k. $$ The $a\_{ijk}$ are called **structure coefficients**. We directly have that: $$ A \cong \left.\mathbb{F}\[b\_1, \ldots, b\_n\] \middle/ \left\<b\_i b\_j-\sum\_{k=1}^n a\_{ijk}b\_k\right\>\_{1\leq i,j\leq n}\right..$$ Now one can define the following decision problem: $$ \\{(A,B)\mid A, B \text{ commutative $\mathbb F$-algebras with basis $b\_1, \ldots b\_n$ and } A\cong B\\}. $$ To specify an isomorphism $\phi:A\rightarrow B$ it is sufficient to write every $\phi(b\_i)$ as linear combination of the elements of a basis of $B$.

Does anything in this definition seem strange to you or do you think that one can work with it?

> **Motivation:** My motivation behind this is to give a very clear definition of the decision problem first to connect it to other problems, i.e. the problem of deciding polynomial equivalence: Given two polynomials $f,g\in\mathbb F\[x\_1, \ldots, x\_n\]$, we say that $f$ is **equivalent** to $g$ if there exists an invertible linear transformation $\tau$ on the variables such that $f(\tau(x\_1), \ldots, \tau(x\_n))=g(x\_1, \ldots, x\_n)$. In other words, two polynomials are equivalent if you can replace every variable by a linear combination of all variables to obtain the other polynomial.

I'm not sure if this helps as a motivation but the connection of this problems is established by constructing finitely generated commutative $\mathbb F$-algebras from the two polynomials that are isomorphic if and only if the polynomials are equivalent. For this I wanted to make sure that the decision problem is defined very clearly.

# Answer
This seems to be consistent with the presentation in *Equivalence of $\mathbb{F}$-algebras and cubic forms*, Agrawal & Saxena (2006).
> 5 votes

# Answer
Computability over mathematical structure is a long and well established area of research. For example, see:

or google for:

* computability algebra
* computable model theory
> 1 votes

---
Tags: computability, terminology, decision-problem
---


# Question
Title: Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)
The question is exercise 1.9 from Arora-Barak's book *Computational Complexity — A Modern Approach*:

---

Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize this as follows: The machine has an infinite array A that is initialized to all blanks. It accesses this array as follows. One of the machine's work tapes is designated as the address tape. Also the machine has two special alphabet symbols denoted by R and W and an additional state we denote by q\_access. Whenever the machine enters q\_access, if its address tape contains 'i'R (where 'i' denotes the binary representation of i) then the value A\[i\] is written in the cell next to the R symbol. If its tape contains 'i'Wa (where a is some symbol in the machine's alphabet) then A\[i\] is set to the value a.

Show that if a Boolean function $f$ is computable within time $T(n)$ (for some time constructible $T$) by a RAM TM, then is is in $\mathrm{DTIME}(T(n)^2)$.

---

The trivial solution by using an additional tape recording pairs (address,value) turns out to be in $\mathrm{DTIME}(T(n)^3)$, since that tape can be of size $O(T(n)^2)$ with $O(T(n))$ pairs while the address of each pair can be of size $O(T(n))$.

# Answer
> 3 votes
You write in the comments:

> Since the address should be written in the tape by a $T(n)$-time Turing Machine, the size (i.e. string length) of the address can not exceed $O(T(n))$.

Can you use a similar argument to improve the bounds

> \[The\] tape can be of size $O(T(n)^2)$ with $O(T(n))$ pairs while the address of each pair can be of size $O(T(n))$.

you mention in the question? You may need to remember what operations are possible in constant time on the RAM, that is using the precise definition the authors use.

---
Tags: complexity-theory, turing-machines, machine-models, simulation
---


title: Concept of reduction and algorithm

text:
# Question
Title: Concept of reduction and algorithm
Suppose that someone found an algorithm A for a NP problem (that is not NP-complete) that uses an algorithm B for PSPACE-complete or #P-complete problem during execution. (Remaining part of the algorithm takes polynomial time.)

Then suppose there is also an algorithm C for a NP problem that uses the polynomial-consuming part of the algorithm A. The rest of the algorithm C is actually an algorithm that solves NP-complete problems.

Then would this mean that PSPACE-complete or #P-complete collapse to NP-complete?

If so or if not, why would it be like that?

I am asking this question, because I seem to get confused during reading my computation textbook.

Edit: I was a bit confused as in (or more accurately scalar function) math, if g(x)=f(h(x)) and g(x)=f(q(x)), h(x) and q(x) must be virtually the same. So, my question was virtually the aforementioned. That was the parallel I was making between algorithm A and C.

# Answer
> 6 votes
I think I see where your confusion arises. Hopefully ;).

Suppose you have a problem $\Pi \in NP$, and two algorithms $\mathcal{A}$ and $\mathcal{B}$ that both solve $\Pi$.

Assume that $\mathcal{A}$ uses algorithm $\mathcal{A'}$ as a sub-algorithm, where $\mathcal{A'}$ is acutally an algorithm for a $PSPACE$-complete problem.

Also assume that $\mathcal{B}$ is the same as $\mathcal{A}$, but instead of using $\mathcal{A'}$ as a sub-algorithm, it uses $\mathcal{B'}$, which is sufficient to solve $\Pi$, but not to solve the $PSPACE$-complete problem.

I think this is the situation you want to describe?

Now I think your confusion comes from assume that because a problem has two different algorithms, that the algorithms must have the same complexity - at least this is what I get from the analogy with the functions.

This isn't true, you can quite happily have an algorithm which solves a problem, but is actually far more powerful (i.e. it can solve a much bigger super-problem) and another algorithm that can only solve the smaller problem. These two algorithms don't really say anything about one another (at least without a lot more information).

To stretch the function analogy to its breaking point, the situation is more like $g(x) \leq f(x)+h(x)$ and $g(x) \leq f(x)+ q(x)$. Sort of. But not really.

# Answer
> 2 votes
I can tell that you are confused from your question, but unfortunately I am not sure what's confusing you, maybe you can add more detail.

Now to answer you question, it is inconclusive given your description. The fact that you *can* solve a problem from one class by solving another problem from another class does not mean that you *need* do so.

The way reduction usually works (assuming you want to show that problem X is "hard" in some sense) is by showing that another problem Y can be solved by solving X plus some easy extra work, where Y is known to be "hard" in some sense.

Now back to your question. Suppose that we want to sort $n$ integers (a problem in NP). We do so by first solving a PSPACE problem, throw away the result, and use quick sort. This is effectively algorithm A that you described, and you can see why this does not say anything about the complexity classes involved.

# Answer
> 1 votes
Luke illustrates one point of confusion; let me point out another one.

Algorithm $A$ for problem $P \in \mathsf{NP}$ uses algorithm $B$ for problem $Q \in \mathsf{PSPACE}\text{-complete}$. Is it possible that $A$ is "fast", that is it is not slower than $\mathsf{NP}$ allows for?

Yes! $Q$ may be harder than $P$, but maybe $A$ only ever calls $B$ with *easy* instances and thus stays within reasonable bounds! For example, $A$ may use $B$ on polynomially many instances of $Q$ of size at most $10$.

---
Tags: complexity-theory
---


# Question
Title: Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals
I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars:

> Assign an ordering $A\_1, \dots, A\_n$ to the nonterminals of the grammar.
>
> for $i := 1$ to $n$ do begin
> $\quad$ for $j:=1$ to $i-1$ do begin
> $\quad\quad$ for each production of the form $A\_i \to A\_j\alpha$ do begin
> $\quad\quad\quad$ remove $A\_i \to A\_j\alpha$ from the grammar
> $\quad\quad\quad$ for each production of the form $A\_j \to \beta$ do begin
> $\quad\quad\quad\quad$ add $A\_i \to \beta\alpha$ to the grammar
> $\quad\quad\quad$ end
> $\quad\quad$ end
> $\quad$ end
> $\quad$ transform the $A\_i$-productions to eliminate direct left recursion
> end

According to this document, the efficiency of the algorithm crucially depends on the ordering of the nonterminals chosen in the beginning; the paper discusses this issue in detail and suggest optimisations.

Some notation:

> We will say that a symbol $X$ is a *direct left corner* of a nonterminal $A$, if there is an $A$-production with $X$ as the left-most symbol on the right-hand side. We define the *left-corner relation* to be the reflexive transitive closure of the direct-left-corner relation, and we define the *proper-left-corner relation* to be the transitive closure of the direct-left-corner relation. A nonterminal is *left recursive* if it is a proper left corner of itself; a nonterminal is *directly left recursive* if it is a direct left corner of itself; and a nonterminal is *indirectly left recursive* if it is left recursive, but not directly left recursive.

Here is what the authors propose:

> In the inner loop of Paull’s algorithm, for nonterminals $A\_i$ and $A\_j$, such that $i \> j$ and $A\_j$ is a direct left corner of $A\_i$, we replace all occurrences of $A\_j$ as a direct left corner of $A\_i$ with all possible expansions of $A\_j$.
>
> This only contributes to elimination of left recursion from the grammar if $A\_i$ is a left-recursive nonterminal, and $A\_j$ lies on a path that makes $A\_i$ left recursive; that is, if $A\_i$ is a left corner of $A\_j$ (in addition to $A\_j$ being a left corner of $A\_i$).
>
> We could eliminate replacements that are useless in removing left recursion if we could order the nonterminals of the grammar so that, if $i \> j$ and $A\_j$ is a direct left corner of $A\_i$, then $A\_i$ is also a left corner of $A\_j$.
>
> We can achieve this by ordering the nonterminals in decreasing order of the number of distinct left corners they have.
>
> Since the left-corner relation is transitive, if C is a direct left corner of B, every left corner of C is also a left corner of B.
>
> In addition, since we defined the left-corner relation to be reflexive, B is a left corner of itself.
>
> Hence, if C is a direct left corner of B, it must follow B in decreasing order of number of distinct left corners, unless B is a left corner of C.

All I want is to know how to order the nonterminals in the beginning, but I don't get it from the paper. Can someone explain it in a simpler way? Pseudocode would help me to understand it better.

# Answer
This is actually not very complicated. I'll assume that epsilon productions have already been eliminated from the language, because that will only obscure the key concept of "left corner".

Form a graph G where the vertices are all the non-terminals of the grammar. Now draw a directed edge from A to B if there is any production rule that looks like "A -\> B\[...\]". The paper calls B a "direct left corner" of A. More generally, some other non-terminal C is called a "left corner" of A if there is some path from A to C along the edges of this graph. This can be done by computing the transitive closure of G, call it H.

The paper suggests ordering the vertices by counting the number of left corners each vertex A has (i.e. how many other non-terminals you can reach from A, or the out-degree of A in the graph H), then sorting them in decreasing order by this number.

One handwavy motivation for this policy is that if there is an important non-terminal (say the starting symbol S) with connections to many other symbols), then it makes sense to purge left-recursion from S early on, because if you leave it till later there will be more copies of S that you need to expand out. I think the explanation in the paper is more convincing, but perhaps less obvious.
> 4 votes

---
Tags: algorithms, context-free, formal-grammars, efficiency, left-recursion
---