# Question
Title: Are real computers finite state machines?
They have finite resources so they can be modeled by finite number of state what is the same that a finite state machine. There are any proof that it is not true?

Thanks.

# Answer
Yes, real computers are finite state machines: they have finite memory so there's a finite number of states the machine can be in. One consequence of this is that a real computer can't recognise $\\{a^nb^n\mid n\geq 0\\}$.

"But hang on a second!" you're saying, "Any idiot could write a program that recognises that language." Well, suppose your computer has $n$ bits of total storage (memory, disk, anything else you might have plugged in). Even if you use all of that storage to count how many $a$'s you've seen, you can only count up to $2^n$. That means your program can't tell the difference between a string that starts $a^{(2^n)}$ and one that starts $a^{(2^n+1)}$.

But you need to consider the scale of these numbers. A typical computer has, say, 1TB of storage. That means that $n=8\times 2^{40}$ and $2^n \approx 10^{2,600,000,000,000}$. In contrast, the number of atoms in the universe is only about $10^{80}$ and some physicists estimate that the universe will cease to exist in any interesting way in only about $10^{100}$ years, which is about $3\times 10^{116}$ nanoseconds. (Fun fact: the number of seconds in a year is within half a percent of $\pi\times 10^7$.)

In other words, your 1GHz computer only has time to read in about $3\times 10^{116}$ characters before the heat death of the universe, and that's a looong way short of the number of characters you need to feed it to verify that it can't actually accept $a^nb^n$. So, in practical terms, you can consider your computer to be a Turing machine instead of a finite state machine.
> 16 votes

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


title: A little help with regular expressions

text:
# Question
Title: A little help with regular expressions
I am trying to create a regular expression that will generate the following language under the {a,b,c} alphabet: all words that do not contain the substring "bbc"

I am having a really hard time understanding how to approach this question. I have done several other questions where a certain substring must be excluded, but this one really messes with my logic.

Thanks in advance

# Answer
Some things I learnt while learning to answer this type of question:

1. Negation isn't easy to express. There are no shortcuts. The resulting expressions may be far more complex than the expression you would get if negation was a basic operator in the expression language - in which case you could write $\neg(.^\*bbc.^\*)$, where $.$ is a shortcut for $(a\cup\neg a)$
2. Lacking $\neg$, the only way to say $\neg a$ for some symbol $a$ is to enumerate all other symbols: $\neg a = (b\cup c \cup d \cup \ldots)$. In Unix-like regular expressions, you can of course use `[^a]`.
3. In compound expressions, you can use left factorization. E.g. $\neg(bbc) = \epsilon \cup \neg b\neg(bc) = \epsilon \cup \neg b(\epsilon \cup \neg c) = \ldots$. The key insight is that this can be made to work with Kleene star expressions, too; I suggest you invent or look up the details yourself.
> 2 votes

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


# Question
Title: Why use $\mu$-calculus and not LTL,CTL,CTL*?
It is known that the temporal logics LTL,CTL,CTL\* can be translated/embedded into the $\mu$-calculus. In other words, the (modal) $\mu$-calculus subsumes these logics, (i.e. it is more expressive.)

Could you please explain/point me to papers/books that elaborate on this matter. In particular, are there concrete fairness, liveness, etc. properties not expressible in the temporal logics but in the $\mu$-calculus?

# Answer
As for a $\mu$-calculus formula not expressible in CTL\*, see this post.

As for texts on the subject, you are likely to get further ahead by reading papers, as these topics are not covered in many books. Still, the Handbook of Modal Logic may be a good start.

As for papers, try:

Expressive power of Temporal Logics

This PhD thesis

Emerson's Model checking and the Mu Calculus

And there are many more. Just google terms like "expressive power", "mu calculus" and "temporal logics".
> 9 votes

# Answer
The $\mu$-calculus is strictly more expressive than LTL, CTL and CTL\*. This is a consequence of a few different results.

The first step is to show that the $\mu$-calculus is as expressive as temporal logics. The main idea for encoding these logics comes from recognizing temporal properties as fixed points. At a very informal level, least fixed points allow you to express properties of a finitary nature and greatest fixed points apply to infinitary properties. For example, *eventually $\varphi$* in LTL defines that there is an instant in the finite future at which $\varphi$ is true, while *always $\varphi$* states that $\varphi$ is true at an infinite number of future time-steps. In terms of fixed points the eventually property would be expressed using a least fixed point and the always property using a greatest fixed point. Following such an intuition temporal operators can be encoded as fixed point operators.

The next step is to show that the $\mu$-calculus is more expressive. The main idea is alternation depth. Fixed points alternate if a least fixed point influences the greatest fixed point, and vice-versa. The alternation depth of a $\mu$-calculus formula counts the number of alternations that occur in it. The operators in CTL can be encoded by $\mu$-calculus formulae with alternation depth $1$. The operators in CTL\* and LTL can be encoded by $\mu$-calculus formulae with alternation depth at most $2$. However, the alternation hierarchy of the $\mu$-calculus is strict, which means that increasing alternation depth in a formula allows you to express strictly more properties. This is why people say the $\mu$-calculus is more expressive than these temporal logics.

Some references:

1. The initial arguments that the $\mu$-calculus subsumes several logics appears in Modalities for Model Checking:Branching Time Logic Strikes Back, Emerson and Lei, 1985.
2. The translation of CTL into the $\mu$-calculus is straightforward. You can find it in the book on *Model Checking* by Clarke, Grumberg and Peled. You can also find it in *Model Checking and the $mu$-calculus* by Emerson or in Ken McMillan's dissertation.
3. The translation of CTL\* into the $\mu$-calculus is involved. Rather than the original, indirect translation, I suggest the paper of Mads Dam on Translating CTL\* into the modal mu-calculus.
4. There is a simpler translation of LTL into what is called the linear-time $\mu$-calculus, in which the modalities operate over traces and not states. See Axiomatising Linear Time Mu-calculus by Roope Kaivola.
5. The alternation hierarchy is studied in The modal mu-calculus alternation hierarchy is strict by Julian Bradfield and in A hierarchy theorem for the $\mu$-calculus by Giacomo Lenzi.

All this is about expressivity not about utility. In practice, people don't usually specify properties as $\mu$-calculus expressions because they might find temporal logics easier to work with. The industrial specification languages differ from both temporal logics and the $\mu$-calculus in their syntax and their expressive power.
> 6 votes

# Answer
It is well known that $\mu$-calculi can express properties that "count modulo a constant", e.g., "*all even steps visit a $A$-state*" which is captured by something like $\mu X.A \land\Box\Box X$. Such properties cannot be stated with the standard TL modalities Until and Next since these modalities are 1st-order definable. See D. C. Kozen's 1983 article.
> 3 votes

---
Tags: logic, simulation, linear-temporal-logic, mu-calculus, computation-tree-logic
---


# Question
Title: Enumerating weighted permutations in sorted order problem
Let $S$ be a set of $n$ integers. Consider the following *weighted permutations problem*.

> Let $m\<n$ be an integer. What is an efficient algorithm to enumerate all subsets of $m$ integers of $S$ such that they are listed in order of the sum of the integers in each subset?

Each subset is a permutation, and each permutation has a total weight that is the sum of the integers in the permutation.

The idea is to come up with an algorithm that is not the trivial algorithm of enumerating all subsets, and then sorting them, i.e. more of a "streaming" type algorithm. That is, efficiency in terms not so much of time but of "small" space.

Maybe this is published somewhere in the literature although I have not seen it.

# Answer
> 2 votes
Seems like a straightforward recursive algorithm, combined with streams (also known as lazy lists or generators), should work. i.e.,

```
def subsets(m, S):
  if m==0:
      return [{}]
  if S is empty:
      return []
  s = min(S)
  S' = S \ {s}
  T = subsets(m, S')
  U = [u.union(s) for u in subsets(m-1, S')]
  return merge(T, U)

```

With the obvious definitions and Python-ish notation. This returns a list in the desired order, i.e., a list of subsets, sorted by the sum of the elements in each subset. Here I haven't provided the `merge` routine, but it can be implemented using the standard algorithm for merging sorted lists.

For clarity of exposition, I've written the above using lists and list comprehensions. However, for an actual implementation, you should use streams (e.g., Python generators and generator comprehensions) rather than lists. If you do that, there's no need to build all of the lists and represent them in memory; the algorithm shown above can proceed in a streaming fashion.

This is the kind of problem where a language with explicit support for lazy evaluation will shine. With lazy evaluation, I believe you can implement a beautiful, elegant solution that looks clean but has excellent memory complexity.

# Answer
> 0 votes
You have $\frac {n!}{(n-m)!m!}$ options for different subsets. And therefore the minimum efficiency of such algorithm is exponential.

---
Tags: algorithms, reference-request, sorting, efficiency, enumeration
---


# Question
Title: Metrics and algorithms for complexity of a graph
I am interested in what sort of metrics are there that try to give a measure of how complex a given graph is, what are the corresponding algorithms, and what is their time complexity. A short description or list of relevant paper would be great.

It might help to say that I have two graphs and I want to somehow tell which one is \`\`more complex." I will use this metric as a heuristic, so I would like to try various metrics on empirical data. (It might help even more if I say that those graphs represent two FSMs.)

# Answer
> 5 votes
You can use all sorts of properties of a graph this way; obviously how good they are for you depends on your purpose.

Non-comprehensive list of graph attributes, for general undirected graphs:

* Compare simple graph attributes: $|V|$, $|E|$, $\frac{|E|}{|V|}$; you must decide if more or less is considered "more complex".
* Obviously if the graph has multiple components, you can use that, as a measure of simplicity *or* complexity; and/or you can consider it multiple separate graphs.
* Treewidth of the undirected graph; computing the treewidth of a graph is exponential-time in the treewidth, $k$; however, you can set $k$ to a constant, and compute the treewidth quickly (wrt. size of the graph) and consider graphs with higher treewidth to be "complex"
* How "planar" a graph is

+ Crossing number (NP-complete problem to compute)
    + Compare the resulting Kuratowski subgraphs when planarity testing fails (such forbidden graphs can be extracted quickly, but there can be a large number of such graphs)

Presumably a higher number means that there are more non-planar crossings required, thus it is more complex.
* Sparseness, average vertex degree, vertex degree distribution

A low average degree, with a nice distribution can indicate an evenly sparse graph, thus perhaps lower "complexity". Easy to compute, simply average the degree of each vertex over all of them; distribution is slightly more complicated I suppose; depends on how you choose to do it; see wikipedia on degree distribution.
* Average eccentricity (see wikipedia on Distance (graph theory)), eccentricity distribution
* Diameter, radius ratios. Example: large diameter, low radius (see (see wikipedia on Distance (graph theory)); test ratios of these on "complex" and non-"complex" graphs, see if it diffrentiates.
* Compare the dimensions of the graphs (NP-hard)
* Have some subgraphs you consider "complex", and test for subgraph isomorphism in your actual graphs (NP-complete), or, use Maximum common subgraph isomorphism (NP-hard)
* Perhaps some sort of compressibility/entropy measure, but this touches on isomorphism; the same graph can be layed-out or represented in a matrix multiple ways, not all of them equally compressible. A canonical graph labeling could help with this, but that is itself difficult.

Some ideas for an FSM:

* Size (though note that you can have equivalent FSMs of different sizes; these measurements are about the graph complexity, not necessarily FSM complexity)
* You can do a topological sort or level structure, and compare them that way; possible measures of complexity: depth, level-width.
* You can do a DFS, and detect cycles; perhaps more cycles == more complex?

Counting cycles can be a hard problem (NP-hard). Perhaps you can find some relaxation for your specific graphs, for example if they are planar (I don't know that counting cycles in planar graph is any easier, but you would start searching for special cases based on what special cases you do know). There are some approximation algorithms for general cycle counting though. See ***Counting cycles in an undirected graph using DFS-XOR algorithm***, (IEEE paywalled off); abstract:

> We present an algorithm for counting the number of cycles in an undirected graph. The given algorithm generates exact results but it is not guaranteed to run in a polynomial time. Afterwards, an approximated version from the algorithm guaranteed to run in a polynomial time was introduced. The obtained results was used to measure the entropy of graphs. Entropy represents robustness of the graph under analysis. An experiment is conducted to compare the results of our algorithm with the results of another algorithm based on the Donald Johnson backtracking algorithm.

# Answer
> 3 votes
It's hard to measure, unfortunately, but the Kolmogorov complexity is generally a good measure. That is, a graph that has lots of "patterns" and can be compressed is less complex that a "random" one which cannot.

# Answer
> 2 votes
this is a very important question and a very advanced topic in some areas that also relates to major computational complexity class separations including P/poly vs NP etcetera. this is because of a close relationship between graphs (mainly DAGs) and computational circuits. here is a very nice survey. there are many other options listed by r.s., and if you are more specific about your application it can help to choose what is most appropriate.

---
Tags: graphs, regular-languages, time-complexity
---


# Question
Title: Pushdown automaton for complement of { ww | ... }
I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams).

So, I already know that $L = \\{ ww \mid w \text{ in } (0,1)^\*\\}$ is not context free. Since CFL are not closed under complement its complement $L'$ is a CFL. I also read somewhere that any odd word is part of $L'$ (what about even length words?). So a pushdown automaton description could be: read one letter and put into stack, then read next letter and remove previous letter from stack. Do this until the end. If one letter is left in the stack at the end then word is odd length thus accept, else reject?

# Answer
> 7 votes
You write

> So, I already know that $L = \\{ww \mid w \in (0,1)\*\\}$ is not context free. Since CFL are not closed under complement its complement $L'$ is a CFL

Indeed $L'$ is context-free, but your argumentation is ...eeuh... nonsense. Shure, CFL are not closed under complement, meaning there exist context-free languages of which the complement is not context-free. In general however the complement of a CFL can be both CFL or non-CFL. Even if the complement of every CFL would be non-CFL \[*which is NOT the case*\] it would NOT follow that the complement of every non-CFL is CFL.

The language $L'$ indeed consists of all strings of odd length (that is a regular language and can be checked without using the stack) plus the strings of even length for which both halves differ. For the latter part see here.

Phrased more explicitly, let $K = \\{ xy \mid |x|=|y|, x\neq y \\}$ be the language from question 307 linked above. My claim is that $L' = K \cup \\{ x \mid |x| \text{ is odd } \\}$, as $L$ equals $\\{ xy \mid |x|=|y|, x= y \\}$. (And so this explains, as you say in your question, why odd and even length strings are treated separately.)

To answer your question *how* to implement this using a PDA, see the problem I have linked and its answers. A little hint. To check a word is of the form $xy$ with $|x|=|y|$, but $x\neq y$ we must be able to write $x=x\_1ax\_2$ and $y=y\_1by\_2$ with $a\neq b$, and both $|x\_1|=|y\_1|$ and $|x\_2|=|y\_2|$. Unfortunately we cannot check both length requirements at the same time. We *can* however test whether $|x\_1y\_2|= |x\_2y\_1|$, and that is enough. Essentially we find the matching positions of $a$ and $b$ without expicitly finding the middle of the string. (This is not at all obvious, please make some drawings.)

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


# Question
Title: Finding farthest item in an array with duplicates
I have an array $A\[\]$ of size $L$, which contains numbers in the range $1 \ldots N$. Here $L\>N$, so the array will contain repetitions. If $x,y$ are two numbers that are both present in the array, define the distance $d(x,y)$ to be the minimum difference in positions where $x,y$ appear, i.e.,

$$d(x,y) = \min \\{|i-j| : A\[i\]=x, A\[j\]=y\\}.$$

Given a number $x$ that is present in the array, I need to find the number $y$ in the array distance from $x$ is as large as possible. In other words, given $x$, I am trying to find $y$ that makes $d(x,y)$ as large as possible (subject to the restriction that $y$ is a number in $A\[\]$).

Can this be done in $o(L)$ time per query? It's OK to do some pre-processing of the array.

For example, suppose the array is $\[1,3,2,3,4,5,3\]$. Then $d(5,3)=1$, since there is a $5$ one position away from a $3$ (a $5$ appears at index $5$ and a $3$ appears at index $6$). If the query is $x=5$, the correct answer is $y=1$, since this makes the value of $d(5,y)$ as large as possible.

# Answer
> 1 votes
Here's a scheme that does $O(L \lg L)$ preprocessing, and thereafter lets you answer query for the value $x$ in $O(rN \lg L)$ time, where $r$ counts the number of times that $x$ is repeated. This will be slightly more efficient than the naive algorithm for values $x$ that don't occur too many times in the array, but inefficient for common values.

Here's how. During preprocessing, we're going to build a map $f$ defined by

$$f(y,i) = \min \\{ j\>i : A\[j\]=y \\}.$$

Similarly, we're going to build a map $g$ defined by

$$g(y,i) = \min \\{j\<i : A\[j\]=y \\}.$$

(We'll also build a set of inverted indices that, given $x$, enables us to enumerate all indices where $x$ appears in $A$.)

Note that these maps $f,g$ help us compute the distance function $d$ efficiently. In particular,

$$d(x,y) = \min \\{ f(y,i)-i : A\[i\]=x \\} \cup \\{ i-g(y,i) : A\[i\]=x \\},$$

which can be computed with $r$ evaluations of $f$ and $r$ evaluations of $g$. Consequently, given $x$, we'll be able to find the value $y$ that maximizes $d(x,y)$ using $rN$ evaluations of $f,g$, by simply trying all possibilities for $y$.

We're going to use the preprocessing to arrange things so we can evaluate $f,g$ at an input of our choice in $O(\lg L)$ time. How do we do that?

Unfortunately, storing $f$ explicitly would take $NL$ space, which is too much. Fortunately, there is a lot of redundancy in $f$: there are long ranges of indices $i,i+1,\dots,i'$ such that $f(y,i)=f(y,i+1)=\dots=f(y,i')$. This is going to help us represent $f$ more compactly. Similarly for $g$.

In particular, we'll store $f(y,\cdot)$ as an interval tree: whenever we have an interval $\[i,i'\]$ such that $f(y,i)=f(y,i+1)=\dots=f(y,i')=\alpha$, then we add a single interval to the tree with the mapping $\[i,i'\] \to \alpha$. In this way, $f$ is stored as $N$ different interval trees. It is possible to show that the total number of leaves, across all of these interval trees, is at most $L+N=O(L)$ (in particular, the tree for $f(y,\cdot)$ has at most $r'+1$ leaves, where $r'$ counts the number of occurrences of $y$ in $A$). If we store these trees as balanced binary trees, their height will be upper-bounded by $O(\lg L)$. Consequently, the total amount of space needed to store these trees is $O(L \lg L)$. You can also show how to generate these trees in $O(L \lg L)$ time. Finally, evaluating $f$ at a point of your choice amounts to a stabbing query in the corresponding interval tree, which takes $O(\lg L)$ time. This shows how to achieve the time complexity quoted in the first sentence of my answer.

---

As an optimization, if $x$ appears in $A$ more than $L/(N \lg L)$ times, you can answer the query in $O(L)$ time using a standard linear scan (skipping the above cleverness). Of course, you can detect quickly which values of $x$ occur that often by using the inverted indices built during preprocessing.

With this idea, we get a scheme that requires $O(L \lg L)$ preprocessing and lets us answer each subsequent query in $O(\min(L, rN \lg L))$ time, where $r$ counts the number of times that the queried value occurs in $A$.

---
Tags: algorithms, arrays, amortized-analysis
---


title: Find Cycle Length

text:
# Question
Title: Find Cycle Length
Suppose I have an undirected graph which is stored as an adjacency matrix. The graph contains a single cycle; all other vertices are isolated.

How can I efficiently find the length of the cycle?

The best I've been able to come up with:

1. Starting at row 0 of the matrix, traverse through rows until an initial `1` is found, say at row `startVertex` and column **k**. Increment a counter.
2. Search column **k** for its other `1`, say at row **j**. Increment the counter.
3. Search row **j** for its other `1` value. Increment the counter.
4. Repeat steps **2** and **3** until a row or column which matches `startVertex` is found.

The complexity of this algorithm is $\mathcal{O}(V^2)$.

Is there a better algorithm out there?

# Answer
$\Omega(V^2)$ is a lower bound on the running time. You can't do better than $O(V^2)$.

Consider a graph $G\_3$ with a 3-cycle $a,b,c,a$ and a graph $G\_4$ with a 4-cycle $a,b,c,d,a$. To distinguish these two graphs, the algorithm must examine the adjacency matrix at one or more cells corresponding to the 5 edges involved in these cycles.

If we randomly permute the vertices, an algorithm that reads a single entry in the adjacency matrix has at most a $5/{V \choose 2} \le 10/(V-1)^2$ probability of hitting one of those 5 edges. Therefore, an algorithm that reads at most $m$ entries in the adjacency matrix has (by a union bound) at most an $10m/(V-1)^2$ probability of reading at least one entry in the matrix that corresponds to one of those five edges. If $m \< (V-1)^2/20$, this success probability is at most $1/2$.

Thus, there cannot be a deterministic algorithm that always succeeds in distinguishing a graph with a 3-cycle from a graph with a 4-cycle, whose running time is at most $(V-1)^2/20$.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Simplest way to check edge set for transitivity
I'm playing around with tournaments and currently have the problem that I need to check whether a given subset of the edges of a tournament is transitive (it need not be acyclic). I'm aware that I can always take the transitive closure of the edge set and see whether it terminates without adding a single edge or not, but I was wondering if there might be a simpler way than that.

Note that I'm specifically going for simplicity, not efficiency; the tournaments I want to check are over a maximum of $7$ vertices, so complexity really isn't an issue. I would prefer simple, easy to implement ways. The simplest I could find so far is Floyd-Warshall, but maybe someone knows anything that's simpler still.

# Answer
> 5 votes
There's a very simple algorithm for this:

```
for each edge (u,v) in the graph:
    for each edge (v,w) in the graph:
        if (u,w) is not in the graph, return "Not transitive"
return "Transitive"

```

Basically, if the graph is not transitive, then you can always find some path of length two $u\to v \to w$ such that the edge $u \to w$ is not present in the graph. If the graph is transitive, there won't be any such path of length 2. So, just check this condition.

---
Tags: algorithms, graphs, transitivity
---


# Question
Title: 3-SAT where variables occur equally many times as a positive literal and as a negative literal
Let $\phi$ be a 3-CNF formula over variables $x\_1,x\_2,\ldots,x\_n$. Every variable $x\_i$, $i \in \[n\]$, occurs equally many times as a positive literal and as a negative literal in $\phi$.

Is it NP-complete to decide the satisfiability of such a formula? Assuming it is, I would be interested in knowing if it has a special name. Has it perhaps also been investigated somewhere?

# Answer
The problem has been studied as $m$P$n$N-SAT problem by Ryo Yoshinaka in Higher-Order Matching in the Linear Lambda Calculus (in 16th International Conference, RTA 2005, Nara, Japan, April 19-21, 2005, Proceedings).

The $m$P$n$N-SAT is a SAT problem where each positive literal occurs exactly $m$ times and each negative literal exactly $n$ times. It has been shown that even $2$P$1$N-SAT is NP-complete. Note that $1$P$1$N-SAT is in P since each variable can easily be removed after a single step of resolution, which doesn't increase the number of clauses in the formula.
> 5 votes

# Answer
It is NP-complete (but I don't know if it has a name): suppose that a variable $x\_i$ appears as a positive literal $n$ more times than as a negative literal.

Then you can "balance" it adding $n$ new 3CNF clauses with $n$ new variables $y\_1,...,y\_n$:

$-x\_i \lor y\_1 \lor -y\_2$
$-x\_i \lor y\_2 \lor -y\_3$
...
$-x\_i \lor y\_{n-1} \lor -y\_n$
$-x\_i \lor y\_n \lor -y\_1$

If $x\_i$ appears more times as a negative literal, apply the same expansion but using $x\_i$ in the new 3CNF clauses instead of $-x\_i$.

The $y\_i$ are balanced and the resulting formula (that can be built in polynomial time) is clearly satisfiable if and only if the original 3CNF formula is satisfiable: whatever is the value of $x\_i$ the new clauses can be satisfied setting $y\_i = true$, so they don't "interfere" with the satisfiability of the original formula.
> 11 votes

---
Tags: complexity-theory, np-complete, satisfiability, decision-problem
---


# Question
Title: Partition points on a 2d plane with arbitrary line segment
Let's say I have a 11x11 grid with a few points (around 8) marked in the grid. One of the points is in the center cell. Call it point P.

I choose a point other than P and connect it with a line segment to P. Call that point C1

I choose another point that is not C1 and connect it with a line segment to P. Call that point C2.

Now, if we extend the line segments out from P to the edges of the grid, then the grid will be split into two regions A and B.

How can I determine which of the remaining points are in A and B efficiently?

# Answer
Hint: Instead of storing them as cartesian points, store them as polar coordinates (with a tiny drop of preprocessing).
> 1 votes

---
Tags: computational-geometry
---


# Question
Title: Corresponding noun for "side-effect-free"?
For functions or computations we have terms like:

* Deterministic – Determinism
* Pure – Purity

Now what is the correct corresponding noun for **side-effect-free**?

"Side-effect freeness"? "Side-effect freedom"? "Non-side-effective"?

# Answer
A good rule of thumb for grammatical questions is, if it's so complicated that you need to ask, it's better to just rephrase the sentence. For example, "Side-effect-freedom of the function guarantees X" is more simply and elegantly written, "Because the function is side-effect free, X is guaranteed" or even, "The function has no side-effects, so X is guaranteed."

Having said that, keywords for articles are expected to be noun phrases so that would be a place to use "side-effect freedom".

(By the way, "non-side-effective" is an adjective.)
> 8 votes

# Answer
The word is *nullipotence*, the noun form of *nullipotent*. From the first definition on Wiktionary:

> (mathematics, computing) Describing **an action which has no side effect**. Queries are typically nullipotent: they return useful data, but do not change the data structure queried. Contrast with idempotent.

(emphasis mine)

http://en.wiktionary.org/wiki/nullipotent
> 9 votes

# Answer
Depending on the context, "absence of side-effects" may be a more readable term.
> 8 votes

# Answer
I learned this concept as referential transparency.

However, there is some debate as to whether or not this is actually a meaningful term, so if you're going to use it in a paper, you should define it first.
> 3 votes

# Answer
Side-effect freedom, is what I would use.
> 2 votes

# Answer
If running the function multiple times has the same net effect on the system as running it once, the function is *idempotent* and has *idempotency*. Don't know if that's what you're looking for.
> 2 votes

# Answer
You almost got it with "side effect freedom". The problem is that this possibly means that the side effects are free (as in "freedom of side effects"). To be clear, you need "freedom from side effects". And note how "free of" does not pair with "freedom of"; both "free of something" and "free from something" go to "freedom from something".

In general, you will find that compound noun phrases whose head is "freedom" are instinctively eschewed by native speakers of English, even though they are grammatical. For instance "freedom of speech" and "freedom from oppression" are not called "speech freedom" and "oppression freedom". The meaning could be worked out from context ("speech freedom" probably isn't "freedom from speech", and "oppression freedom" isn't "freedom to oppress") but the forms are simply not *euphonic*. Even if that is merely from disuse, it is the way it is.

Academic papers in CS are also written for a world audience which includes non-native English speakers. If you're able, then write like a native English speaker.
> 1 votes

# Answer
You probably want "orthogonality". It seems to fit your definition exactly.
> -1 votes

---
Tags: terminology, programming-languages
---


# Question
Title: Proving that the language SPACE TMSAT is PSPACE-complete?
I'm trying to prove that the language SPACE TMSAT (where SPACE TMSAT = {⟨$M$, $w$, $1^n$⟩ : DTM $M$ accepts $w$ in space $n$}) is PSPACE-complete.

My solution is as follows:
SPACE TMSAT $= \\{\<M,w,1^{n}\> :$ DTM $M$ accepts $w$ in space $n\\}$ can only be computed by running machine $M$ on $w$. As this forces the allowance of the computation of any PSPACE language, SPACE TMSAT is PSPACE-complete.

Does this solution make sense? Am I being too hand wavy? Any other suggestions or critiques? Thanks!

# Answer
> 2 votes
To prove that a problem $P$ is PSPACE-complete, you need to do two things:

1. Show that $P$ can be computed in PSPACE.
2. Show that every problem $Q \in $PSPACE reduces to $P$, in the sense that there exists a polytime function $f$ such that $f(x) \in P$ iff $x \in Q$.

As mentioned by *dkuper*, you forgot about the first part. Your argument for the second part (PSPACE-hardness) unfortunately does not constitute a proof. You need to follow the definition: given an arbitrary $Q \in $PSPACE, produce a polytime function $f$ such that $f(x) \in P$ iff $x \in Q$.

Apart from not being a proof, your argument is also not convincing: there could be some trick that avoids simulating $M$. Such tricks are behind results such as L=SL or NL=coNL in complexity theory. For example, the second result states that given a non-deterministic Turing machine $M$ that runs in logarithmic space, there is a ways to decide non-deterministically in logarithmic space whether a given input is *not* accepted by $M$. The obvious way to do this is to run all possible execution paths of $M$, but since $M$ could make polynomially many non-deterministic decisions, that would require polynomial space (we need to keep track of all these decisions so that we can run through all of them). Yet there is a trick that enables us to do it non-deterministically using only logarithmic space.

Hint for the second part: Given $Q$, consider a Turing machine $M$ that computes $Q$ in space $O(n^k)$ for some $k$.

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


# Question
Title: Computability of the function $P(x)=\varphi_x(x)$
Let $P$ be the predicate on natural numbers defined by $P(x) \iff \varphi\_x(x) = 1$ where $\varphi\_x$ is the $x$-th computable function. Show that $P$ is not computable.

# Answer
This is the standard argument by diagonalization. Let the $x$-th computable map be $\varphi\_x$.

Suppose $P$ were computable, which by definition means that the following function $p$ is computable: $p(x) = (\mathsf{if}\ \varphi\_x(x) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0)$. Therefore the function $f(x) = 1 - p(x)$ is computable also. There is a number $y$ such that $\varphi\_y = f$. Either $p(y) = 0$ or $p(y) = 1$:

* if $p(y) = 0$ then $$0 = p(y) = \\ (\mathsf{if}\ \varphi\_y(y) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ 1 - p(y) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ 1 - 0 = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ \mathsf{true} \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = 1,$$ a contradiction.
* similarly, if $p(y) = 1$ then $$1 = p(y) = \\ (\mathsf{if}\ \varphi\_y(y) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ 1 - p(y) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ 1 - 1 = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ \mathsf{false} \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = 1,$$ a contradiction.

We have reached a contradiction, so our initial assumption that $P$ is computable is fasle.
> 2 votes

---
Tags: computability
---


# Question
Title: Analysis and classification based on data points
I'm not sure if this is the correct stack exchange or correct tags, but my question is as follows:

I am working on a sort-of ratings system for players in a particular game. After allowing the ratings to develop for many games, I have set up a "database" (not sure if this is the correct term) for matches: a point in the database would consist of the score difference between the players (i.e if it's \>0 player 1 won) and the rating discrepancy between the two players before this match.

The idea is to use this database in order to predict the score difference of a match that has not yet occurred: I measure the rating discrepancy between the 2 players, and lookup in my database for the score differences in games of a "similar" rating discrepancy, and based on these games I am able to predict, say, a rough probability of each score difference occurring in this match that has not yet happened.

I actually have two questions:

1) what is a good approach to using the database to predict the probability of each score difference, i.e what qualifies as a "similar" rating discrepancy, how do I deal with extreme cases where the rating discrepancy is very large and I have few data examples of such matches (should I relax my definition of "similar"?), etc. A bit of googling shows that maybe I am looking for something relating to data clusters.

2)how would I go about implementing an algorithm as above? are there good standard implementations of such classification algorithms? I am writing in C# if it makes a difference.

# Answer
One option is to use the Elo rating system. It is based upon some mathematical theory of the sort you are mentioning.

The Bradley-Terry model is another mathematical approach that may also interest you. It assumes that each player has an (unknown) strength, which can be quantified as a real number, and the probability that Alice beats Bob is determined by some smooth function of the difference of their strengths. Then, given the pairwise win/loss records, it estimates the strength of each player.

See also:
> 2 votes

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


title: Hidden Markov Model in Tagging Problem

text:
# Question
Title: Hidden Markov Model in Tagging Problem
I try to understand the details regarding using Hidden Markov Model in Tagging Problem.

The best concise description that I found is the Course notes by Michal Collins.

The goal is to find a function $f(x)=arg max\_{y \in Y} p(y|x)$, where $y$ is the tag set for sentence $x$.

**Question 1**. It's suggested to use a generative model and to estimate joint probability $p(x,y)$ from the trainig examples, however what the the reason to use generative model and increase the number of computation why not directly to estimate $p(y|x)$, I think it's possible to estimate the conditional probability straightforward from the training data.

**Addendum**. Do you know the reason why at all we should try to use a generative model in this case (POS tagging). As I understand if we can estimate $p(x,y)$ that exactly with the same success we can estimate $p(y|x)$ and directly find the answer to the question, what is the best tagging - $\hat{y}$ without weak assumption of generative model. There is the reason to use generative model, and I don't see it yet. Can you explain me what the reason?

**Question 2.** Assume we decided to use a generative model and made estimation to $p(x,y)$ why we decide to decompose it as follows $p(x,y)=p(y)p(x|y)$ and not $p(x,y)=p(x)p(y|x)$?

**Addendum**. I do understand that it's very logical to use the decomposition $p(y)p(x|y)$ just because by doing it we approach $p(y|x)$, so mathematically it seems very reasonable, however according to the task I don't see what the problem to decompose it like $p(x,y)=p(x)p(y|x)$, there should be sore reason why we can not decompose it so and I don't understand why.

I appreciate your help.

# Answer
> 1 votes
1. You can directly estimate $p(y|x)$, this is what you're doing when using a Conditional Random Fields (CRF) for tagging. As someone else said, this is called a discriminative model. A major advantage of discriminative models for tagging is they allow one to easily incorporate arbitrary features (starts with a capital letter, contains a number, contains punctuation, etc). This isn't easy with generative models since doing so would usually violate the the independence assumptions required to make $p(x|y)$ tractable. Ultimately which one is better will depend on your particular problem.
2. If you're doing classification, and you can build a good model of $p(y|x)$, then what would you be messing with the joint for? When using a generative model for classification the idea is to "sneak up" on the distribution of interest, namely $p(y|x)$, because it is hard to model explicitly. One way to do this is by observing that $p(y|x) \varpropto p(y,x) = p(y)p(x|y)$.

# Answer
> 1 votes
**Answer 1**

You *can* try to directly fit the function $\Pr\[y | x\]$. This is called a discriminative classification. This is typically solved via some regression mechanism such as ordinary least squares, or lasso, or ridge depending on certain assumptions of the model.

**Answer 2**

The reason we want to factor $\Pr\[x, y\] = \Pr\[x | y\] \Pr\[y\]$ is because we are interested in the *class conditional* density $\Pr\[x | y\]$. That is, what is the probability of observing data $x$ given the label $y$?

There are various pros and cons to both discriminative and generative classification. For example, generative models tend to be easier to fit \[naive Bayes is maximized simply by counting, whereas discriminative requires solving some convex optimization problem\]. However, discriminative models typically faire better under independence assumptions when fitting data.

---
Tags: machine-learning, natural-language-processing, hidden-markov-models
---


# Question
Title: Can a Turing Machine decide only non-regular languages?
I have an assignment where i need to create a Turing machine that decides an infinite language $L\subset \\{0,1\\}^\*$ for which all $L'\subseteq L$, if $|L'|=\infty$, then $L'$ is not a regular language.

I think this is not possible due to Rice's Theorem. It's not possible to tell for a Turing Machine if a language is regular or not.

Moreover, on any given input, the machine can loop so it cannot decide an infinite language $L$.

Is this the right answer? It seems too easy to be the answer... Any input would be appreciable. Thanks in advance.

# Answer
> 1 votes
@Karolis Juodele already gave the answer, and your answer is also correct.

Another thing to keep in mind is although infinite languages can be undecidable, some of them are regular.. ex. $\\{0\\}^\* \subset \\{0,1\\}^\*$ is an infinite language but is regular (you can construct a FSM, with a single state, that accepts it).

Basically any undecidable language is infinite, but any infinite language is not necessarily undecidable.

Also, for a language like $L = \\{w \mid m \text{ halts on the input } w\\}$, there exists a Turing Machine for which $L$ is undecidable.

---
Tags: formal-languages, regular-languages, turing-machines, automata
---


# Question
Title: Is my proof for a context free language correct? Same number of a's as b's
I have the following grammar G: $$ \begin{align\*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align\*} $$

I am going to prove that this language L(G) consists of words with the same number of a's and b's by strong induction.

**Inductive hypothesis**: $S$ produces $m$ $a$'s and $m$ $b$'s, $A$ produces $m+1$ $a$'s and $m$ $b$'s, $B$ produces $m$ $a$'s and $m+1$ $b$'s for some integer $m$.

**Base**: The smallest string produced by $S$ is $ab$ or $ba$. The smallest string produced by $A$ and $B$ is $a$ and $b$ respectively. All three satisfy the IH.

**Induction**: Assume the inductive hypothesis is satisfied for all strings of length $k$ or less.

For strings of length $k+1$:

**(1)**. $A\to aS$; then $S$ inductively derived a string of length $k-1$ with same number of $a$'s as $b$'s. Since $A$ is initiated by $S\to bA$, we concatenate that $b$ plus the $a$ in $aS$ and we get a string of length $k+1$ with same number of $a$'s as $b$'s.

**(2)**. $A\to bAA$; then each $A$ on the right hand side has one more $a$ than $b$. Since $A$ is initiated by $S\to bA$, we concatenate that $b$ plus the $b$ in $bAA$ and we get a string of length $k+1$ with the same number of $a$'s as $b$'s.

Can I continue for $B\to bS$ and $B\to aBB$? Am I totally wrong here?

# Answer
> 2 votes
First of all, you've never said what exactly you are trying to prove. From the title, one might guess that you're trying to prove that the given grammar generates the language $L = \\{ w \in (a+b)^\* : \\#\_a(w) = \\#\_b(w) \\}$. However, it seems that you are only trying to prove that every word generated by the grammar is in $L$. (The other direction is even harder.)

In order to prove your claim, you strengthen the claim, trying to prove the following:

1. If $S$ generates $w$ then for some $m \in \mathbb{N}$, $\\#\_a(w) = \\#\_b(w) = m$.
2. If $A$ generates $w$ then for some $m \in \mathbb{N}$, $\\#\_a(w) = m + 1$ and $\\#\_b(w) = m$.
3. If $A$ generates $w$ then for some $m \in \mathbb{N}$, $\\#\_a(w) = m$ and $\\#\_b(w) = m + 1$.

In order to prove the strengthened claim, you need to prove by induction some claim $P(m)$. However, you never state what $P(m)$ is. Your "inductive hypothesis" is actually the statement that you're trying to prove by induction. One way to interpret your inductive hypothesis is the following: $P(m)$ states that

1. If $S$ generates $w$ then $\\#\_a(w) = \\#\_b(w) = m$.
2. If $A$ generates $w$ then $\\#\_a(w) = m + 1$ and $\\#\_b(w) = m$.
3. If $A$ generates $w$ then $\\#\_a(w) = m$ and $\\#\_b(w) = m + 1$.

However, this is simply false. You need to come up with a predicate $P(m)$ that you could prove by induction. Once you've done that, you can check whether your proof works.

The rest of your proof contains several other problems, but let's start with the more major problems mentioned above.

---
Tags: formal-languages, context-free, formal-grammars, proof-techniques
---


# Question
Title: Can we push and pop both at a single transition in a PDA?
Let say I have a pda :

δ(q1,a,Z)=(q2,aZ)

δ(q2,a,aZ)=(q2,bZ)

Is this allowed....

you can see that in **δ(q2,a,aZ)=(q2,bZ)**, we are basically popping 'a' and pushing 'b' for a single transition...

Is this allowed for PDA ??

# Answer
(Previously a comment)

Depends on how you define PDAs. The definition I consider canonical certainly does allow you to exactly this: it is assumed that each transition pops the top-most symbol, and pushes an arbitrary string. To represent not changing the stack, you'd push the same symbol you just popped; to pop one symbol, you'd push the empty string; to put $w$ on top of the stack, you'd push $wa$ (where $a$ is the top-most symbol); and to replace $a$ with $b$, you'd push $b$.
> 2 votes

---
Tags: pushdown-automata
---


# Question
Title: Tiling an orthogonal polygon with squares
Given an orthogonal polygon (a polygon whose sides are parallel to the axes), I want to find the smallest set of interior-disjoint squares, whose union equals the polygon.

I found several references to slightly different problems, such as:

I am looking for an algorithm for minimal *tiling* with *squares*.

# Answer
> 16 votes
I will try to show this problem is NP-hard, by reduction from $\text{Planar-}3\text{-SAT}$.

---

# Reduction from $\text{Planar-}3\text{-SAT}$

## Some basic Gadgets

Gadgets are internal configurations of geometry that will allow us to construct gates for use in a circuit, to which we will reduce $\text{Planar-}3\text{-SAT}$.

### **4X3-gadget**

This gadget has two valid **minimal-square-partition-states**:

**Left**A **4X3-gadget**.**Middle and right:**Two possible **minimal-square-partition-states**.

### **5X4-gadget**

This gadget, is exactly like a **4X3-gadget**, just with larger dimensions.

**Left**A **5X4-gadget**.**Middle and right:**Two possible **minimal-square-partition-states**.

### **endpoint-gadget**

An **endpoint-gadget** *is* a **5X4-gadget**. It is frequently used as an endpoint/pin of a **gate**. One of the two states of an endpoint can be valued as true, and the other false. An endpoint marks the two ends, one as $T$ and the other as $F$. **The end that is covered by the large square is the value of the endpoint.**

**Left:** Wireframe of **endpoint-gadget**. **Center:**True-valued endpoint. **Right:** False-valued endpoint.

### **i-wire gadget**

An **i-wire gadget** is short for **implication wire**.

**Rules:**

* An **i-wire gadget** consists of a odd-length rectangle of a length of more than $2$ and a width of $2$.
* An **i-wire gadget** can have $3$ **minimal-square-partition-states**, pushed from one side, the other, or neither; an **i-wire** in this third state shall be called **locally unconstrainted**.

Example:

**Figure 7:** An **i-wire gadget** of length $7$, and width $2$.

Here is how it is used:

**Figure 8,9**, **Left:** wireframe **i-wire across** two **endpoints**. **Right:** Union.

Now, if one **endpoint** is in the right state, it forces the other **endpoint** into a pushed-position. Example:

**Left:** Square partition diagram; left switch is down, "pushes" all the squares down the **i-wire** and finally, pushes the other switch (**endpoint**). **Right:** Square partition diagram; left **endpoint** is full, "pushes" all the squares down the **i-wire**, and forces the **endpoint** on left to be "up".

This is essentially a logical implication. Consider "down" to be true, then we have $A \implies \neg B$. We can also do $A \implies B$ by simply flipping the endpoint on the right.

However, this leaves the unconstrainted case:

If we combine two **i-wires**, we can get a two-way implication, essentially a boolean (in)equality:

So, two **i-wires** can carry a full equality relationship, much like a circuit - in fact, it *is* a circuit. We will use these pairs to construct a usable **wire**.

Each **i-wire gadget** contributes $\frac{l-1}{2}+2$ partition-squares to the **minimal-square-partition**, save for the shared-corners with other gadgets.

**i-wires** can be oriented as needed.

## **wire**

A **wire** consists a pair of **i-wires** that are connected to the same **gates** at each endpoint.

* The **i-wires** are colored red and green.
* The pair must be separated by $3$ spaces (convention).
* Each gate pin will have a green and red contact; a wire must correctly connect.
* ***Invariant rule:*** one **i-wire** be pushed in the opposite direction of the other **i-wire**, each gate assumes this, and makes certain of this (unless otherwise noted).
* Since each wire contains a two-way implication, it carries the values from gate to gate like a wire in a circuit.
* **Every *wire* must be connected to a gate at both ends.**. Failing this can ruin the assumptions of some gates that I describe, and the invariant rule above; however, gates that have **endpoints** *across the leads* are safe - you can connect stray wires to these **endpoints** without worrying about it ruining the gate.
* **wires** must be of odd-length, *including* the leads to any circuit it connects to; however I will describe an **odd-skip-gate** below that allows an even-lengthed wire to become odd-lengthed.

**Pictures**:

**Above:** A **wire**.

**Left and right:** Two possible **minimal-square-partition-states** of a **wire**. Note that if the wire is only this length, it will not be able to shift off to the right or left, and will have to break one square into smaller pieces.

**wires** can be oriented as needed.

### **bend-gate**: Bending a **wire**

**Left:** Wire-frame view. **Right:** Union view.

Note the use of the **4X3-gadget**. It is used to fix the red lead to odd length.

Following are the two possible **minimal-square-partition-states** of the bend:

**Left and right:**Two possible **minimal-square-square-partition-states** of a bending wire.

The gate can be oriented as needed. Obviously, this gate can be mirrored to work for the other direction.

### Skewing a **wire**

It is easy to shift a wire over. Wireframe illustration:

## **named-value-gate**

A **named-value-gate** is essentially an endpoint as a gate with one wire contact:

### **odd-skip-gate**: Odd skipping a **wire**

Sometimes it is inconvenient to only have odd-length wires. For example:

As you can see, that little bit of extension is a bit annoying. Here is a corresponding solution, using the **4X3-gate**:

So, turning this into a gate, we get the **odd-skip-gate** (in wireframe):

The gate can be oriented as needed.

### **twist-gate**: Twisting a **wire**

Somtimes you get the red and black **i-wires** on the wrong sides for use with a **gate**. In this case, a **twist-gate** is provided, to twist the red and black **i-wires** to the opposite sides.

Wireframe illustration:

Convince yourself it works:

Start from $A$, follow the push-arrows, everything else should be forced and consistent.

The gate can be oriented as needed.

### **split-gate**: Splitting a **wire**

Splitting a wire, wireframe:

Convince yourself that it works:

**Figure:**Start from $A$, follow the push-arrows. Everything should be forced and consistent.

**Figure:**Start from $A$, follow the push-arrows. Everything should be forced and consistent.

**Note:** Every wire coming in and out of the splitter **absolutely must** connect to an endpoint somewhere, in order to maintain the invariant. Alternatively, you can add endpoints to each of the pairs of leads of the splitter.

The gate can be oriented as needed.

## **not-gate**

The not gate takes a wire and outputs a wire that has the reverse implications. It is basically a **twist-gate**, except that it relabels the colorings of the wires. The **not-gate** looks like this:

And a view of the two possible states:

The gate can be oriented as needed.

## **clause-gate**

For the **clause-gate**, we first introduce the **clause-gadget**:

**Left to right:** **1** **clause-gadget**. **2-4:** $3$ different **minimal-square-partition-states**.

This is what the gate looks like:

We can demonstrate the different states of this gate (explanation underneath all $3$ illustrations):

Explanation:

2. Start at the **clause-gadget** and follow the arrows.
3. Non-arrow-lines mean that it is part of a circuit, but it is not forced into a state by the gate.
4. The state of the **clause-gadget** forces one of the endpoints to be valued **true**.

As you can see, at least one of the inputs will have to be valued as **true**. This is exactly what a $3\text{-CNF}$ clause requires.

The gate can be oriented as needed.

## Reduction

Let $\Phi(\mathbf x)$ be a $\text{Planar-}3\text{-SAT}$ formula, where

$$\Phi\left(\mathbf x\right)={\huge\wedge}\_i^n C\_i,\\ C=\left\\{(x\_j \vee x\_k \vee x\_l)\right\\} $$

A visual aid (original source: Terrain Guarding is NP-Hard (PDF), reproduced in tikz):

Then:

1. For each variable $x\_i\in\mathbf x$, place two **named-variable-gates** next to each-other, name one of them $x\_i$ and the other $\neg x\_i$.
2. Connect the gates to each-other with a **not-gate**, so that they logically negate each-other's values.
3. Place the variables' gates' polygons at their locations in the planar-embedding.
4. For each clause, place a **clause-gate** at the clause's location in the planar-embedding.
5. Using the gates described above, connect all the variables to their clauses.
6. Run a **minimum-square-paritioning-algorithm** on the resulting union of the all of gate's polygons (the entire circuit).
7. If the algorithm returns the sum of all the gate's **minimal-square-partition-state** sizes (subtracting for shared-corners) then it is satisfiable. If it is not satisfiable, it will force a constrained gadget to split into smaller squares, thus increasing the number of squares required to partition the circuit.

## Why it works

* Each gadget has a **minimal-square-partition-state** size; that is, a **minimal-square-partition** of that gadget is a certain size.
* Some gadgets have several states with this size; each of these states are valid **minimal-square-partitions**.
* When gadgets are combined only in the corners, the sum of the **minimal-square-partition-states** of the gadgets is \*still the **minimUM-square-partition-state** of the union of them; you can see this intuitively: joining at the corner does not give ample space for a square to expand/connect with a square from another gadget.
* While combining gadgets at the corner does not decrease the **total minimum-square-partition size**, it *does* relate and constrain the gadgets with each-other.
* With the gates shown above, you can constrain the states enough, so that if the logical formula is unsatisfiable, then one or more gadets will have to break into even smaller squares, and increase the **minimum-square-partition size**.

### graph sources

You can also see larger images by removing the "s", "m", "l", suffixes of the imgur urls. For example, You can see a larger image of this: https://i.stack.imgur.com/6CKlGs.jpg by going to https://i.stack.imgur.com/6CKlG.jpg. Notice the missing "s" before the `.jpg`.

# Answer
> 8 votes
An old paper I coauthored establishes that the covering problem is polynomial for a polygon without holes, and NP-complete with holes. We showed that a key underlying graph is chordal. Please note: the algorithm is polynomial in the number $N$ of unit squares in the polygon, $O(N^{3/2})$.

> "Covering orthogonal polygons with squares." L. J. Aupperle and H. E. Conn and J. M. Keil and Joseph O'Rourke. *Proc. 26th Allerton Conf. Commun. Control Comput.*, pp. 97-106, 1988. (link to download PDF scan)

However, the resulting covering may include squares that overlap. You are looking for a tiling, where squares are not permitted to overlap, so your problem is not quite the same.

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


# Question
Title: Is there a low degree vertex in planar graphs?
A book I read states "Since $G$ is planar, $G$ has a vertex $v$ of degree at most 5".

1. Is this true?
2. Why?
3. Does this theorem have a name?

# Answer
1. Yes, this is true.
2. It is a direct consequence of Euler's formula. The formula entails that the average degree is strictly less than 6, which implies the existence of a vertex of degree at most 5.
3. It doesn't have a name in itself, but Euler's formula is the overall subject.
> 6 votes

---
Tags: graphs
---


# Question
Title: Negative weight cycle vs maximum weight cycle
I'm having trouble understanding why it's easy to detect negative-weight cycles (Bellman Ford) but hard to find the maximum weight cycle in an undirected graph.

If we negate the weight of each edge, we can easily find if there are any cycles with total weight \> 0. However it must not be easy to find if there are any cycles with weight \> 1 or else we could repeat with 2, 3, 4 etc until the answer is no.

Is this correct? Why is it so much harder to detect if there exists a cycle with weight \> 1 then to find if there is a cycle with weight \> 0?

# Answer
> 3 votes
I don't think it's very surprising that finding a single negative-weight cycle is easier than finding the highest-weight cycle. If you ask me to find a negative-weight cycle, I can find any one and, if I give you what I claim is an answer, it's very easy for you to check the sequence of vertices and see that the weight really is negative. But the maximum-weight cycle feels like a very special object. Even if I claimed to have found it how would I convince you that there isn't another cycle with even higher weight?

On the other hand, maybe this intuition isn't helpful, since it's also trivial to check that a given cycle has weight at least 1 or 2 or 17...

# Answer
> 1 votes
This is an excellent question. I don't have a fully satisfactory explanation, but let me give you a start at it.

First off, it's important to understand that we can't solve this problem by simply enumerating all cycles and checking the weight of each one. Why not? Because there can be (and often are) exponentially many cycles. Therefore, merely enumerating them will necessarily take exponential time -- too long to be feasible.

So how does Bellman-Ford work? It works by some clever trick that avoids the need to individually examine each cycle one by one. Instead, it builds up a summary that summarizes something about the effect of all paths and cycles of length up to $n$. Effectively, for each vertex $v$, it summarizes all paths that start at $v$, end at $v$, and take at most $n$ steps. Since every cycle must contain a path of this form, the summary somehow encapsulates the effect of all possible cycles.

Why can't we use this to detect (say) whether there exists a cycle of weight $\ge 1$? It's because Bellman-Ford's summary includes paths that walk around the cycle multiple times. If the cycle is of length $k$, then it's gonna includes paths of length $n$, i.e., paths that walk around the cycle about $n/k$ times. For instance, if you have a cycle of length $n/3$, then the summary includes a path that walks around the cycle three times.

What's the effect of walking around a cycle multiple times? If you want to distinguish positive-weight cycles from cycles whose weight is not positive, walking around a cycle multiple times does no harm. If the cycle has positive weight, then you can walk around it a few times and the total weight will still be positive. If the cycle's weight is not positive, then you can walk around it a few times and the total weight will still be non-positive. So if all we care about is the difference between positive vs non-positive weight, walking around the cycle multiple times does no harm.

But now consider how things change if what we care about is the difference between "weight $\ge 1$" vs "weight $\< 1$". If we have a cycle whose weight is $\< 1$ and we walk around that cycle multiple times, the total weight might become $\ge 1$. For instance, if the weight of the cycle is $1/2$ and we walk around the cycle three times, then the total weight of that path is $1.5$, which is $\ge 1$: we started with a cycle of weight $\< 1$ and ended up with a path of weight $\ge 1.5$. This fact totally screws up Bellman-Ford and makes it useless for checking whether there exists a cycle of weight $\ge 1$. (Do you see the difference?)

I realize this isn't a 100% satisfactory answer. It tells you why Bellman-Ford isn't going to work to solve your problem. However, it doesn't give you any intuition to explain why this is difficult in general (e.g., why it's hard to find some other algorithm to solve it). I don't have a really good intuition for that -- maybe someone else will have a better explanation for you. In the meantime, maybe this gives you a start at getting your head around why this problem is hard.

# Answer
> 0 votes
Deciding $weight \geq c$ is still easy for any constant $c$ and integer edge weights. I can check all cycles of length $c$ in $O(n^c)$ (assuming unit weights). But what if $c$ is not a constant, for example $c=n/2$? It wouldn't be polynomial anymore.

On the other hand with the general decision problem (i.e. when $c$ is not constant) we can decide the Hamiltonian cycle problem which is NP-Complete.

# Answer
> 0 votes
Let us consider the simpler versions of these problems where edges are unweighted.

1. Given a graph $G$, check if $G$ has a cycle.
2. Given a graph $G$ and a number $k$, check if $G$ has a cycle of length at least $k$.

The first one is easy and can be solved using DFS. The second one is NP-hard.

---

Let's look at an even simpler problem:

1. Given a graph $G$ and two vertices $s$ and $t$, check if there is a simple path from $s$ to $t$ in $G$.
2. Given a graph $G$ and two vertices $s$ and $t$ and a number $k$, check if there is a simple path from $s$ to $t$ in $G$ of length at least $k$.

All of these problems are of the same flavor. The top one is easy while the bottom one is NP-hard. I will explain the difference for the last one because it is simpler but the same explanation applies to the other pairs.

The reason that the top ones are easy while the bottom ones are not is the result of **the structure of the answers** for these problems.

Let's first look at the problem of finding a simple path and try to solve it recursively. If we just try to solve this problem directly we would need to keep track of the vertices that we have used so far:

> $SimplePath(s,t,G) :=$ there is a path from $s$ to $t$ in $G$.
>
> $SimplePath(s,t,G)$ iff
> $s=t$ or for some $u\in G$ $SimplePath(s,u,G-t)$ and $ut \in G$.

If we try to solve the problem with this naive recursive algorithm it will take exponential time: *there exponentially many possibilities for the set of unused vertices!* We have to be smarter.

Why did we get exponentially many possibilities? Because we were trying to find a *simple* path and to enforce this condition we needed to keep track of unused vertices.

OK, so let's drop that condition and see where we can get:

Consider the problem of a finding a path (not necessary simple) from $s$ to $t$. Since the path doesn't need to be simple we don't need to keep track of unused vertices. In other words, the graph doesn't change over time.

> $Path^G(s,t) :=$ there is a path from $s$ to $t$.
>
> $Path^G(s,t)$ iff
> $s=t$ or
> for some $u\in G$ $Path^G(s,t)$ and $ut \in G$.

But we are not done yet. The issue is that we don't know if $Path^G(s,u)$ is a smaller problem than $Path^G(s,t)$. So this recursive solution might end in a loop and never terminate.

To avoid this we can add an extra parameter that makes sure the problem gets smaller: the number of edges in the path.

> $Path^G(s,t,k) :=$ there is a path from $s$ to $t$ with at most $k$ edges.
>
> $Path^G(s,t,k)$ iff
> $k=0$ and $s=t$ or
> $k\>0$ and for some $u\in G$ $Path^G(s,u,k-1)$ and $ut \in G$.

Now note that there is a simple path from $s$ to $t$ iff there is a path from $s$ to $t$ with at most $n$ edges. In other words:

> $SimplePath(s,t,G)$ iff $Path^G(s,t,n)$.

The essential points here are:

1. Every (nontrivial) simple path from $s$ to $t$ consists of a simple path from $s$ to some vertex $u$ and an edge $ut$.
2. We can assume that $t$ does not appear in the simple path from $s$ to $u$.
3. We don't need to explicitly keep the list of unused vertices.

These properties allow us to have a **smart recursion** for the existence of a simple path problem.

Now these do not apply to the problem of finding a path of length at least $k$. We don't know how to reduce the problem of finding a simple path of length at least $k$ to a smaller subproblem without keeping the list of unused vertices. Those properties allow us to solve the existence of path problem efficiently.

When a graph doesn't have a negative cycle they allow us to solve the existence of a path of length at most $k$ problem and the shortest simple path problems efficiently.

However they don't hold for the existence of a path of length at least $k$. Consider a graph with $3$ vertices $s, u, t$. $w(su) =1000, w(st) =1000, w(ut)=10, w(tu)=10$. The path of length at least $1001$ from $s$ to $t$ contains $u$ and the path of length at least $1001$ from $s$ to $u$ contains $t$. So we cannot reduce an instance of the problem to a smaller instance of the problem without explicitly giving the list of unused vertices.

In other words, we don't know a smart recursion for the existence of a simple path of length at least $k$ problem while we do know a smart recursion for the existence of a simple path.

---

Coming back to the last part of your question, there is problem with your argument.

It is indeed the case that the existence of a cycle of length $\>k$ can be solved in polynomial time for any *fixed* $k$ (i.e. $k$ is not part of the input). (Similar to how one can check if an unweighted graph has a cycle of length $k$ in time $O(n^k)$.)

However when $k$ is part of the input this does not hold any more since the running time depends on $k$ in a bad way.

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


title: CNF Generator for Factoring Problems

text:
# Question
Title: CNF Generator for Factoring Problems
I've been reading these:

I don't understand how the reduction from FACT to $3\text{-SAT}$ works. Are there any simple articles in which I can read about it?

My final goal is to eventually implement a reduction from $3\text{-SAT}$ to the undirected Hamiltonian circuit problem.

# Answer
> 6 votes
> I don't understand how the reduction from FACT to 3-SAT works. Are there any simple articles in which I can read about it?

Most of the reading material assumes several steps of knowledge.

* First, you should read about how logic circuits (logic gates) work.
* Optionally learn or use a simple multiplication algorithm. You might want to start with the long-multiplication algorithm that everyone learns in school.
* Then research and understand a multiplication circuit, and/or learn how to convert the chosen algorithm to a circuit.
* You should now know how to make a simple multiplication circuit (MULT). Next learn to extend it for $n$-bit numbers.
* Once you have a circuit, you can force the outputs of the circuit to the $N$ value you want to factor. You do this by taking the $n$ outputs, and point-wise **xor**ing them together with your $N$ value. Set the *final output* to be true iff $N$ and the MULT output cancel each-other out. You can do this by first **or**ing all the **xor** results; if they are all $0$, then the output matched $N$ (in this case, set the final output to be $1$, else $0$).
* Now you have $\text{Circuit-SAT}$. Learn about $\text{Circuit-SAT}$.
* $\text{Circuit-SAT}$ asks if there is an input that can satisfy the output. $\text{Circuit-SAT}$ is an NP-complete problem, that is almost directly convertible to $3\text{-SAT}$ (when you get to this step, you will understand this pretty easily)
* There is a straightforward reduction from $\text{Circuit-SAT}$ to $3\text{-SAT}$ available here: Convert Circuit SAT to 3-SAT

You can't get it all in one scoop without talking to someone in-person. Rather you should follow the steps, without skipping. *Each of these* has "simple" material to learn from; but you'll not find one that teaches you everything in one sitting from the very basics.

---

Also see **Computer Organization - Module II**, section **2.5.1 Array Multiplier**, which implements a **carry-save-array-multiplication circuit**:

Looks a lot like grade-school multiplication, doesn't it ...

Each box is (FA means "Full adder", which is also on that page in section **2.2 Serial & Parallel Adder**):

# Answer
> 3 votes
there are several ways to conceptualize this, esp using the psychological concept of chunking which is rougly equivalent to the use of "abstraction(s)" in CS. what part is hard to understand? the conversion of factoring to SAT is much easier to understand if you learn how EE circuits implement binary arithmetic (mainly addition), and to note that multiplication is repeated addition of a shifted multiplicand, and in binary multiplication, this is reduces to bits of the multiplier simply "masking" the shifted multiplicand.

the SAT formula specifies, via a set of constraints, a relation between "input" and "output" bits equivalent to binary multiplication. it is actually like a 2-way computation device because it naturally computes in a forward direction $f(x,y)= x \cdot y = z$ and in a "reverse" (inverse) direction $f^{-1}(z)=x \cdot y$.

for multiplication implemented in SAT, specify the "input" bits, and leave "output" bits unassigned (via what are called "unit clauses") and solve the CNF formula for "output" bits. for factoring, specify the "output" bits without specifying the "input" bits.

in EE addition circuits are called "half/full adders". then the only task is to convert these circuits into SAT (CNF) formulas. binary addition of bit vectors is done most simply with a string of full adders where each carry bit feeds into the next stage of the addition, the so-called "ripple carry adder".

here is a nice slideshow on converting binary/bitvector arithmetic to propositional logic aka "bitblasting". on slide 8 the CNF formula for a full adder is given. slide 10 has the same ripple carry adder.

---
Tags: algorithms, graphs, reductions, factoring, hamiltonian-path
---


title: Why is SAT not in P?

text:
# Question
Title: Why is SAT not in P?
I'm studing P and NP complexity classes. I like know, why is SAT not in P? Is it because I can not determine if any Boolean expression is satisfiable?

# Answer
It is possible to determine whether a boolean expression is satisfiable, the question is how quickly it can be done.

If there are $n$ variables, then we can try all $2^{n}$ possible truth assignments, and eventually we'll find if there is a satisfying one, but this is not *polynomial* time with respect to the size of the input.

There *might* be some polynomial time algorithm that does solve SAT, we don't know, however SAT is NP-complete, which gives strong evidence that there isn't a polynomial time algorithm. It all comes down to whether P=NP or not.
> 5 votes

---
Tags: complexity-theory, satisfiability, p-vs-np
---


# Question
Title: Convert a non-deterministic Turing machine into a deterministic Turing machine
How can we systematically convert a non-deterministic Turing machine into a deterministic Turing machine that recognizes the same language?

# Answer
The deterministic machine simulates *all* possible computations of a nondeterministic machine, basically in parallel. Whenever there are two choices, the deterministic machine spawns two computations. This proces is sometimes called dovetailing. The tape of the deterministic simulator contains a list of configurations of the nondeterministic one, and performs a step on each of these in turn. This requires quite some administration, and the capability to move aroud data when one of the simulated configurations extends its allotted space.
> 7 votes

# Answer
a worthwhile question because the algorithm is not really so trivial to a neophyte and worth studying for its key/basic theoretical implications, and your question is not specifically limited to recursive languages! a key is to recognize the algorithm as a breadth first search of a (possibly infinite) graph of all possible transitions, ie exploration of all edges of a graph in parallel so to speak. (exercise: explain why the similar graph-traversal algorithm, depth first search cannot work.)

the construction is relevant to, and shows up in, the famous/fundamental Cook proof for the NP completeness of SAT. basically solutions of the SAT construction are 1-1 correspondence with NTM acceptance paths in P-time.

moreover there is significant theory (somewhat similar/analogous) of converting other nondeterministic machines to deterministic ones eg NFAs to DFAs. in general the complexity of the corresponding classes (deterministic vs nondeterministic ones) is open for many related questions.

see also
> 4 votes

---
Tags: turing-machines, simulation
---


# Question
Title: How to prove that the minimum square partition of a 3X2 rectangle has 3 squares
This question is motivated by an older question about tiling an orthogonal polygon with squares.

Given a $3\times 2$ rectangle like the first image, the second image is a *square partition* of that rectangle.

* A *square partitioning* is a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
* A *minimum square partitioning* is a *square partitioning*, for which is no *square partitioning* that is made of a lesser number of squares.

> How can we prove that the second image is a *minimum square partitioning* of the $3\times 2$ rectangle?

Can we generalize this to ${\rm M{\small IN}S{\small QUARES}}(R\_{w,h=w-1})=w$? (see followup question )

# Answer
> 3 votes
The case $w = 3$ is somewhat boring. Here is how to show that you need at least three squares. There is some square $S\_1$ touching the bottom-left corner. There is some square $S\_2$ touching the bottom-right corner. These squares must be different. At least one of them doesn't go all the way to the top, and so one of the other two corners remains uncovered, requiring another square.

I'm not sure how to extend this proof beyond $w \> 3$. Let me just mention that a classical result of Dehn shows that if an $h \times w$ rectangle can be tiled by squares then $h/w$ is rational, and moreover there is some integer $c$ such that if you scale everything by $c$ then all squares have integer sides.

---
Tags: proof-techniques, computational-geometry, tiling
---


# Question
Title: Prove that two different concatenations of relations are equivalent
I've had this question on my exam today and I couldn't figure it out, I would like to know the answer.

The question:

> Given relations $R$, $S$ on a set $U$.
>
> $R$ is transitive, $S$ is reflexive.
>
> Prove that $(R;S;R)^2$ is a subset of $(R;S)^3$.

Partial answer of mine:

> By using associativity you get an equivalent question of:
>
> Prove that $R;S;R;R;S;R \subseteq R;S;R;S;R;S$.
>
> By monotonicity you have that $R;S;R \subseteq S;R;S$.
>
> Then I took $(x, y) \in R;S;R$, so there exist $a, b \in U$ such that $xRa \land aSb \land bRy$.
>
> Now I need to conclude that $xSa \land aRb \land bSy$.

Here I am stuck, nowhere I see how I should be using that $R$ is transitive and $S$ is reflexive, and I know they are obvious hints. I tried using them directly, proving by contradiction, but I am just stuck.

# Answer
> 2 votes
Here is an answer without using the algebra of relations (but otherwise identical to phs's). Suppose that $a(R;S;R)^2b$. Then there exist elements $c,d,e,f,g \in U$ such that $$ aRc, cSd, dRe, eRf, fSg, gRb. $$ Since $R$ is transitive, $dRe$ and $eRf$ imply that $dRf$. Since $S$ is reflexive, $bSb$. Therefore $$ aRc, cSd, dRf, fSg, gRb, bSb. $$ In other words, $a(R;S)^3b$.

# Answer
> 2 votes
This is best carried out using notations from algebra of relations.

You're asked to prove $RSRRSR \leq RSRSRS$. That $R$ is transitive means $RR\leq R$, so $RSRRSR \leq RSRSR$ by monotonicity of composition. That $S$ is reflexive means $I\leq S$, where $I$, the identity relation, is neutral element for composition: $I\leq S$ entails $(RSRSR)I\leq (RSRSR)S$ (monotonicity of composition again). Finally, you have

$(RSR)^2 = RSRRSR \leq RSRSR = RSRSRI \leq RSRSRS = (RS)^3$

as required.

---
Tags: discrete-mathematics
---


# Question
Title: How to solve this big O notation of a fraction
I want to estimate with big O the following expressions:

$$ \begin{align\*} f\_1(x) &= \frac{x^4 + x^2 + 1}{x^4 + 1}, \\ f\_2(x) &= \frac{x^3 + 5 \log x}{x^4 + 1}. \end{align\*} $$

How do you eliminate the constant on the bottom of the fraction? How would you work to solve these types of problems?

# Answer
> 5 votes
The idea is that $x^4 + x^2 + 1 = \Theta(x^4)$, and similarly $x^4 + 1 = \Theta(x^4)$. So the first expression is $\Theta(x^4)/\Theta(x^4) = \Theta(1)$. The second expression can be estimated similarly.

This sort of calculation shows the advantage of asymptotic notation - irrelevant details disappear and calculations become manageable.

# Answer
> 4 votes
If you want to abstain abuse of notation, you can proceed as follows. Compute the limit the ratio for $x \to \infty$:

$\qquad\begin{align\*} \lim\_{x \to \infty} \frac{x^4 + x^2 + 1}{x^4 + 1} &= \lim\_{x \to \infty} \frac{1 + \frac{1}{x^2} + \frac{1}{x^4}}{1 + \frac{1}{x^4}} \\ &= \frac{\lim\_{x \to \infty} 1 + \lim\_{x \to \infty} \frac{1}{x^2} + \lim\_{x \to \infty} \frac{1}{x^4}}{\lim\_{x \to \infty} 1 + \lim\_{x \to \infty} \frac{1}{x^4}} \\ &= \frac{1 + 0 + 0}{1 + 0} \\ &= 1 \end{align\*}$

Note that in the first step is just fraction arithmetics and the second uses rules of calculations with limits; check for yourself that these are valid steps (in particular, all the "small" limits are finite).

Now, by definition of $\sim$ (asymptotic equivalence) we get that $x^4 + x^2 + 1 \sim x^4 + 1$ which implies

* $x^4 + x^2 + 1 \in \Theta(x^4 + 1)$,
* $x^4 + x^2 + 1 \in O(x^4 + 1)$ and
* $x^4 + x^2 + 1 \in \Omega(x^4 + 1)$.

Of course, this calculation generalises to all polynomials: for $P$ a polynomial of degree $k$ with positive dominant coefficient $a\_k$ we have that $P(x) \sim a\_k x^k$ holds.

Your second example works similarly but you get $0$ as limit; this, by definition, implies $x^3 + 5\log x \in o(x^4 + 1)$.

# Answer
> 1 votes
$O(-)$ does not "solve" things or "estimate" them. I'm not just being pedantic: from the way you phrase the question, I think you've misunderstood at quite a fundamental level. To see where I'm coming from, imagine I asked you, "How do I solve the number $x\geq \tfrac34+\tfrac13$?" Maybe I don't understand how to add fractions but I probably wouldn't have written the question that way if adding fractions was my only problem.

Remember what $f(x)=O(g(x))$ means: there are constants $x\_0$ and $c$ such that, for all $x\geq x\_0$, $|f(x)|\leq c|g(x)|$. Just as there are infinitely many numbers greater than or equal to $\tfrac34+\tfrac13$, there are infinitely many functions that are eventually bigger than $f$, whatever function $f$ you choose. In particular, just as $x=\tfrac34+\tfrac13$ is a trivial answer to my question, $g(x)=f(x)$ is a trivial answer to, "Name a function $g$ such that $f=O(g)$."

I hope that helps you understand the concepts better; Yuval and Raphael have already given answers that should give more practical help with these particular examples.

---
Tags: asymptotics
---


# Question
Title: Algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality
I am searching for an algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality( $\text{weight}(u,v) \le \text{weight}(u,w) + \text{weight}(w,v)$ for all vertices $u, v, w$).

My first naive try was to use an algorithm for solving the all-pairs-shortest-path-problem and compare the result to the vertices connecting two nodes directly.

However, I think this might be overkill. Is there any better way to check?

Thanks a lot.

# Answer
> 7 votes
Yes. If you have a complete graph, the simplest algorithm is to enumerate all triangles and check whether each one satisfies the inequality. In practice, this will also likely be the best solution unless your graphs are very large and you need the absolute best possible performance. For instance, enumeration will likely be faster than most shortest-paths algorithms.

None of the shortest-path algorithms provide better asymptotic runtime; they are more complicated to implement; and they will be slower in practice (because of a larger constant factor).

As AJed correctly points out, you can use matrix multiplication to beat the $O(n^3)$ bound. However, this requires a bit more care. While there are algorithms for matrix multiplication that are faster than $O(n^3)$ time, the algorithms are tricky to implement, so if you take this approach, you might want to use an existing library/implementation (e.g., BLAS). Also, the asymptotically optimal algorithms (e.g., Coppersmith/Winograd, Stothers, Williams) only become faster once $n$ becomes extremely large so they won't be worthwhile in practice. This suggests that if you want to wring out every last bit of performance, you'll need to actually benchmark this on realistic workloads: asymptotic complexity can be misleading.

If you care about extreme optimization, cache effects may also play a huge role here, so the way the graph is laid out in memory may have a significant effect on the constant factors. Fortunately, if your graph is represented as an adjacency matrix, standard libraries for matrix multiplication already take this into account.

If it were me, I'd just enumerate all triangles and check the triangle inequality. If you run into a problem domain where this is the bottleneck in the overall computation and where it is too slow, then you could consider more sophisticated approaches, like using matrix multiplication, at that point. To paraphrase Knuth, "Premature optimization is the root of all evil".

# Answer
> 3 votes
Assume a complete graph containing $n$ vertices and $m$ edges.

For the all-pairs shortest path approach, this can be done using Johnson's algorithm in $O(nm + m^2 \log n)$ time, the Floyd-Warshall algorithm in $O(n^3)$ time or the tropical representation in $O(n^4)$ time.

Depending on the input size, you may be best off by just listing out each triangle, testing the inequality then reporting the outcome in $O(n^3)$ time by observing that a complete graph has $\begin{pmatrix} n \\ 3\end{pmatrix}$ triangles which can be listed using a simple brute-force algorithm.

Papers by Latapy \[1\], Schank and Wagner \[2\] offer algorithms for listing and counting triangles in complete and other types of graphs which may provide you with some more ideas.

\[1\] Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs by Matthieu Latapy (LIAFA - CNRS, Universite Paris 7)

\[2\] Finding, Counting and Listing all Triangles in Large Graphs, An Experimental Study\* by Thomas Schank and Dorothea Wagner, University of Kalrsruhe, Germany

---
Tags: algorithms, graphs
---


# Question
Title: Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers
I have the following problem, which seems to be similar to Set Cover.

We are given a set $U$ of elements (the universe, e.g., $U=\\{1,2,3,4,5\\}$). We're also given a set $S$ of subsets (e.g., $S=\\{\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\},\\{1,2,5\\},\\{1,3,4\\},\\{2,3,4,5\\}\\}$).

The standard set cover problem asks for the minimum subset of $S$ that covers the whole universe $U$, i.e., the smallest set-cover. In our case this would be $\\{\\{1\\},\\{2,3,4,5\\}\\}$.

However, I'm interested in finding a collection of set-covers where each subset from $S$ is used at most once. I want to find the largest such collection possible, i.e., to find as many different, disjoint set-covers of $U$ as possible. Considering our example, the three set-covers $\\{\\{1\\},\\{2,3,4,5\\}\\}$ and $\\{\\{3\\},\\{4\\},\\{1,2,5\\}\\}$ and $\\{\\{2\\},\\{5\\},\\{1,3,4\\}\\}$ would be the output, since each one is a set-cover of $U$ and they are pairwise disjoint (no subset from $S$ is used in more than one set-cover).

Just testing all possible combinations of set-covers is definitely not an option. I have tried using an algorithm for set cover (ILP implementation) repeatedly, eliminating all used subsets in between runs. However, I'm certain that this strategy does not actually maximize the number of all possible covers.

**Edit 1:** I will try to describe the size of my problem a bit better. The typical size of $U$ is about 4000. $S$ consists of about 50 subsets. Each element of $S$ covers on average about 70% of $U$. Please keep in mind that I don't want to find *all* subset combinations out of $S$ that cover $U$. I just want to determine the maximum number of set covers using each subset from $S$ *only once* (or not at all). As of now I'm guessing the maximum number of possible covers is approximately 5.

# Answer
> 2 votes
The desired output from your algorithm might be exponentially large. (There could be exponentially many set covers). Therefore, you can't possibly expect to have an efficient algorithm in general.

One approach could be to code this up as a SAT (or ILP) problem, and add blocking clauses, so that in each iteration it gives you a new set cover that you haven't seen before. Whether this will be effective in practice will depend upon many factors, such as how many set covers exist.

To help us help you, I suggest you tell us more about the parameters and structure of your particular problem. What would be a typical size of $|U|$ and of $|S|$? What would be a typical number for the total number of set covers (the size of the output that you're hoping to produce)? Is there any structure in $S$ that might be helpful? The best algorithm for your particular situation is likely to depend upon these factors.

---

**Edit:** Thank you for the additional details! That helped. So, it sounds like your goal could be described: given $k$, test whether there exist $k$ disjoint set covers from $S$ (i.e., test whether there exists $C\_1,C\_2,\dots,C\_k$ where $C\_i \subseteq S$, $C\_i$ is a set cover, and $C\_i \cap C\_j = \emptyset$ for all $i,j$). This is the decision problem version of your problem; if we can solve the decision problem, then we can use binary search on $k$ to find the maximum number you're looking for.

Given your problem size, the first thing I'd try would be using a SAT solver. Here's how you could formulate your problem in a way that would let you apply an off-the-shelf SAT solver. Suppose $S=\\{s\_1,s\_2,\dots,s\_{50}\\}$, where each $s\_i$ is a subset of the universe $U$. Introduce boolean variables $x\_{i,j}$ (where $1 \le i \le 50$ and $1 \le j \le k$), with the intent that if $x\_{i,j}$ is true, then the $j$-th cover $C\_j$ will include $s\_i$ (in other words, the $j$-th cover contains the subsets $\\{s\_i : x\_{i,j} \text{ is true}\\}$). We obtain the following constraints, which can each be expresses as CNF clauses:

* For each $i$, at most one of $x\_{i,1},x\_{i,2},\dots,x\_{i,k}$ is true. One way to express this is as the conjunction of clauses $(\neg x\_{i,j\_1} \lor \neg x\_{i,j\_2})$ over all $j\_1 \ne j\_2$, i.e.,

$$\bigwedge\_{1 \le j\_1 \< j\_2 \le k} (\neg x\_{i,j\_1} \lor \neg x\_{i,j\_2}).$$

(Other ways of encoding this constraint are described here.) This expresses the constraint that the $k$ set-covers are disjoint.
* For each $j$, $\\{s\_i : x\_{i,j} \text{ is true}\\}$ is a set cover. In other words, for each $j$ and each $u \in U$, there exists $i$ such that $u \in s\_i$ and $x\_{i,j}$ is true. This can be expressed as the following conjunction of clauses:

$$\bigwedge\_{j,u} \bigvee\_{i : u \in s\_i} x\_{i,j}.$$
* Optionally, you could break the symmetry here by imposing a lexicographic order on the set-covers. For instance, you could require that when $1 \le j\_1 \< j\_2 \le k$, then $(x\_{1,j\_1},x\_{2,j\_1},\dots,x\_{50,j\_1}) \< (x\_{1,j\_2},x\_{2,j\_2},\dots,x\_{50,j\_2})$ (using the lexicographic ordering on bit-strings of length 50).

You could then try using an off-the-shelf SAT solver and see if it is able to complete on this problem in a reasonable amount of time.

---
Tags: algorithms, optimization, set-cover
---


# Question
Title: What is the minimum square partition of an almost-square rectangle?
This question is motivated by an older question about tiling an orthogonal polygon with squares. It is a generalisation of my former question about how to prove that the minimum square partition of a 3X2 rectangle has 3 squares).

Let:

* An *almost-square-rectangle* be a rectangle that has a width $w$ and height $h=w-1$.
* A *square partitioning* be a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
* A *minimum-square-partitioning* be a *square partitioning*, for which is no square partitioning that is made of a lesser number of squares.

Illustration:

**Top row:** The **almost-square-rectangles** of widths $3$, $4$ and $5$. **Bottom row:** Are these **miminum-square-partitions** of their corresponding rectangles?

My question is now:

> What is the minimum-square-partitioning of an almost-square-rectangle?
>
> Can we prove ${\rm M{\small IN}S{\small QUARES}}(R\_{w,h=w-1})=w$?

Note a follow-up question, Minimum square partitions for 4x3 and 5x4 rectangles.

# Answer
> 6 votes
A similar question was asked on Mathoverflow. The commenters mentioned a paper of Kenyon, which shows that the minimum number of squares required to tile a $w \times (w-1)$ rectangle is $\Theta(\log w)$. See also a related paper of Walters.

---

You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).

---
Tags: computational-geometry, tiling
---


title: Dynamic subtraction game

text:
# Question
Title: Dynamic subtraction game
I came across the following dynamic subtraction game:

> There is one pile of n chips. The ﬁrst player to move may remove as many chips as desired, at least one chip but not the whole pile. Thereafter, the players alternate moving, each player not being allowed to remove more chips than his opponent took on the previous move. What is an optimal move for the ﬁrst player if n = 44? For what values of n does the second player have a win?

Now, I know how to solve basic subtraction games, i.e., when both the players are allowed the same set of moves throughout the game (e.g., subtract only 1, 2, or 3 throughout the game). But in the game mentioned above, this set of possible numbers for subtraction is not fixed. I have no clue how to go about solving this question. Any kind of help would be appreciated.

# Answer
> 1 votes
Hint: A player loses if they are presented with a pile of size 1. If presented with a larger pile, what should you do if it's the first move of the game?

---

Here is a more general solution, which will be applicable in other cases.

You can find the winner (and even the Sprague-Grundy function) using dynamic programming. Each *state* of your game consists of a pair $(n,B)$, where $n$ is the number of chips, and $B$ is an upper bound on how many chips you're allowed to remove. I'll let you figure out the edges of this dag and the starting state. Now you scan the graph from the sinks up: a sink (state with no outgoing edges) is a LOSE state (from the point of view of the player whose turn it is to play). A state leading only to WIN states is a LOSE state, otherwise it's a WIN state, and any edge pointing at a LOSE state is a winning move.

It's probably more challenging to find a general formula for which player wins the game given $n$, but one way would be to compute it empirically for several values of $n$ (or more generally, of $n$ and $B$), figure out a formula, and prove your formula.

---
Tags: algorithms, dynamic-programming, game-theory
---


title: conversion of this grammar to CNF

text:
# Question
Title: conversion of this grammar to CNF
My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$

after removing lambda productions: $S\to SS, S\to (S), S\to(), S\to S$

after removing unit productions: $S\to SS, S\to (S), S\to()$

I got upto this point. Do not know how this grammar will be in CNF coz I am not sure if using () makes the grammar illegal. Need help how to proceed and make this grammar in CNF?

# Answer
Yes, the grammar you noww have is still illegal. For CFG you can only have two types of productions $A\to BC$ and $A\to a$ where $A,B,C$ are nonterminals (variables) and $a$ terminal.

It is best to add additional variables that introduce the brackets $A\to ($ and $B\to )$. Now you can use $S\to AB$ instead of your production $S\to ()$.

Finally, try to get rid of $S\to (S)$. It is too long and contains both terminals and nonterminals on the right side.
> 3 votes

---
Tags: context-free, formal-grammars, normal-forms
---