# Question
Title: Hard computational problem on special class of bipartite graphs
I am interested in the properties of a class of bipartite graphs $G(X \cup Y, E)$ where all nodes in $X$ are 3-regular, all nodes in $Y$ are 2-regular, and $|X|=|2Y/3|$. First, Is this a well known class of graphs? Secondly,

> Is there an example of intractable computational problem restricted to this class of bipartite graphs?

# Answer
Given a 3-regular graph $G = \\{V,E\\}$ you can build a bipartite graph $G'$ with the required properties picking $X = V$ and $Y = E$ and for every edge $e\_k = (u\_i,u\_j) \in E$ add edges $(u\_i, e\_k), (e\_k, u\_j)$. So I think that you can find some hard problems starting from hard problems on 3-regular graphs.

For example SUBGRAPH ISOMORPHISM is NP-hard for your class of graphs.

The reduction is from Hamiltonian cycle on 3-regular graphs: given a 3-regular graph $G$, build the corresponding $G' = \\{X \cup Y, E'\\}$ and check for a subgraph $H'$ which is a closed simple cycle of length $2|V|$. $G'$ has a subgraph isomorphic to $H'$ if and only if $G$ has an Hamiltonian cycle.
> 4 votes

# Answer
These graphs are the incidence graphs of cubic graphs, a.k.a. 2-stretches of 3-regular graphs. I'll write $I(G)$ for the incidence graph of $G$.

Given a graph $G$ and an integer $k$, it's NP-complete to determine if $G$'s **crossing number** is at most $k$ (i.e., whether $G$ can be drawn in the plane with at most $k$ edges crossing each other), even if $G$ is restricted to be cubic. Clearly, the crossing number is not affected by adding an extra vertex in the middle of each edge. (Source: Hlineny, "Crossing number is hard for cubic graphs", *J. Combin. Theor. B* 96(4):455–471; DOI.)

It's possible that the **bandwidth** problem for these graphs is NP-complete, since it is NP-complete for trees where every vertex has degree at most three. (Source: problem GT40 in Garey and Johnson for general graphs; for low-degree trees, Garey, Graham, Johnson and Knuth, "Complexity results for bandwidth minimization", *SIAM J. Appl. Math.* 34:477-495; Citeseer.)

Various NP-complete graph problems remain so on cubic graphs and these lead to NP-complete problems on the corresponding incidence graphs that are reasonably natural. For example, asking if a cubic graph $G$ has a dominating set of size at most $k$ is equivalent to asking if $I(G)$ is a union of at most $k$ copies of $I(K\_{1,3})$. Likewise, an independent set in the cubic graph corresponds to a set of disjoint copies of $I(K\_{1,3})$ in $I(G)$.
> 3 votes

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


# Question
Title: Big O Notation - Find a Function That Represents the Statement
There's an `f(n)` such that `f(n) != O(f(n/2))`

so by the definition of big O notation:
for `f(n) = n^2` the statement is false, because there is a constant c such that `n^2 = c*(n^2/2)`

Which f(n) will work?
My guess is f(n) = 2. is that correct?

# Answer
`f(n) = 2` does not work, no, because there is a constant c such that `2 = c*(2/2)`, namely c = 2. The function you're describing is a constant function, which is normally written O(1).

Any function of the form `f(n) = a * n^b` will not work (with the constant `c = 2^b`), but exponential functions will.

If we let `f(n) = k^n`, then we have `O(f(n/2)) = c * f(n/2) = c * k^(n/2) = c * sqrt(k^n)`. Then we could find

```
f(n) < O(f(n/2))
k^n < c * sqrt(k^n)
sqrt(k^n) < c
```

By choosing n large enough, we could always invalidate this inequality; so there is no such c.

To briefly cover some other functions, anything of the form: `f(n) = n!` `f(n) = k^(n^n)` or `f(n) = (a^n) / (n^b)` will work, anything of the form `f(n) = n^a * (log(n))^b` `f(n) = n^a */ (log(n))^b` will not work.

anything "approximately" exponential or faster will work, anything "approximately" polynomial or slower will not.
> 1 votes

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


# Question
Title: Find subset with minimal sum under constraints
Let $M$ be a finite set of even cardinality. Define $C=\\{\\{a,b\\}:a,b \in M, a \neq b\\}$ the set of all pairs over $M$. Let $w:C \rightarrow \mathbb{R}^+\_0$ be a function.

Now find $C' \subset C$ with the following constraints:

$$ \bigcup C' = M \\ \forall x,y \in C': x \cap y = \emptyset \\ \sum\_{x \in C'}w(x) \text{ minimal} $$

In words: Find a subset $C'$ of pair-wise disjunctive pairs over $M$ that covers $M$, with the sum of these pairs being minimal. Any element of $M$ must appear in exactly one pair.

I could not find an efficient algorithmic solution, and I also fail to relate this to any other known (optimization) problem. I was thinking of the subset sum problem, but I don't see any relation.

So the questions is: Can you find an efficient algorithm to find $C'$? A good approximation might also be sufficient. If not, can you reduce this to any other known computer science problem?

# Answer
> 5 votes
Your problem is known as *minimum-weight perfect matching*, and can be solved in polynomial time using several different algorithms. One algorithm that can be used is Edmonds' Blossom algorithm. See also Cook and Rohe, who discuss how to implement Blossom.

---
Tags: algorithms, reductions, optimization
---


# Question
Title: Why are bytes treated like the base unit?
If bits are the base unit of information, why are bytes treated like the base unit?

For example, usually values are expressed in Mega/Giga/Tera/Exa bytes instead of bits. I am aware that bits are sometimes used (e.g. sometimes for internet speed), but generally to me it seems like bytes are used as if they are the base unit instead of bits.

# Answer
> 1 votes
CPUs operate in machine words and in bytes, but never in single bits. Old CPUs (say 8086/8088 and 80286) had machine words of length 16 bits, which were separated into two halves of 8 bits. Machine code could operate on each of these bytes separately. Memory could also be read in byte chunks, though in reality memory was always read in machine words (the 8088, however, apparently read its memory byte by byte), and nowadays in even larger cache lines.

Another reason to consider bytes is that files are stored as sequences of bytes (nowadays, actually in multiples of a larger unit, the disk *sector*). There are two reasons for that: one is that CPUs are byte-oriented, and the other is that encodings such as ASCII and EBCDIC use bytes as their atomic unit of data (that is, each byte stores one character). This legacy is still with us - if you read binary data from a file, it will come up with chunks whose length is measured by bytes (even if in practice data is read to a much larger buffer), and the length of a file is measured in bytes.

# Answer
> 2 votes
For historical reasons.

In the early days and even so today a byte represented the most commonly used data.

A byte represents one character in ASCII.

A byte was and still is the size of the instruction for the most commonly used opcodes at the assembly level. Having the most common instructions in one byte saved the most amount of memory.

It is a power of two so 8 is better than 7,6, and 5.

You can get two BCD digits in one byte.

---
Tags: information-theory
---


title: CNF SAT conversions

text:
# Question
Title: CNF SAT conversions
I am interested in reductions from 3-CNF boolean expressions to similar restricted forms. For example, I am interested in knowing how to reduce a 3-CNF formula to another 3-CNF formula where each variable appears in at most $b$ clauses. I observed this is used in MAX-SAT so I am interested in knowing such reductions. Is there a paper/book that contains descriptions of such forms and their properties?

# Answer
> 5 votes
Feige's classical paper A threshold of ln n for approximating set cover shows that 3SAT-5 is NP-complete; this is the version of 3SAT in which each variable occurs *exactly* 5 times. The general trick here is to include clauses stating $a \leftrightarrow b$, thus allowing "duplication" of variables. If you're very careful, you can get to the symmetric situation considered by Feige.

(On the subject of set cover, recently Dinur and Steurer showed that it is NP-hard to approximate set cover better than $\ln n$, using a reduction of Moshkovitz. Feige's result relies on a stronger assumption.)

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


title: Theorem Proofs in Coq

text:
# Question
Title: Theorem Proofs in Coq
# Background

I am learning assistance, Coq, on my own. So far, I have completed reading Yves Bertot's *Coq in a Hurry*. Now, my goal is to prove some basic results concerning the natural numbers, culminating with the so-called division algorithm. However, I have encountered some setbacks on my way towards that goal. In particular, the two following results have proved (pun intended) to be more difficult to prove in Coq than I initially imagined. In fact, I have, after many fruitless attempts, resorted to prove them by hand (as shown below). This is clearly not helping me become more proficient in handling Coq; which is why I turn to this forum. My hope is that someone on this site is able and **willing** to help me translate my proofs below into a proof that Coq accepts. All help is sincerely appreciated!

## Theorem A

For all $x,y \in N$ \begin{equation} x \< S(y) \subset x \< y \lor \text{I}(N,x,y) \end{equation} **Proof:**

Suppose $x \< S(y)$. Hence there is a $z \in N$ with \begin{equation} \text{I}(N,x+S(z),S(y)) \tag{\*}\end{equation} Hence by (Peano 1b and 3) \begin{equation} \text{I}(N,x+z,y) \end{equation}

Define a predicate \begin{equation} Q(u):=(\text{I}(N,x+u,y) \subset x\<y \lor \text{I}(N,x,y) \end{equation}

It is sufficient to show $Q(z)$. We prove this by induction on $z$. To see $Q(0)$, not ethat if $\text{I}(N,x+0,y)$ holds then $\text{I}(N,x,y)$ is true by Peano 1a. Thus, $x\<y \lor \text{I}(n,x,y)$. Now, we prove $Q(S(v))$: Suppose $\text{I}(N,x+S(v),y)$. From this definition we have $x\<y$ and thus $x\<y \lor \text{I}(N,x,y)$ also in this case. Finally, Peano's fifth axiom gives $Q(z)$ and by $(\*)$ we get $x \< y \lor \text{I}(N,x,y)$. \begin{equation} \tag{$\square$} \end{equation}

## Theorem B

For all $x,y \in N$ \begin{equation} x \<y \lor \text{I}(N,x,y) \lor y\<x \end{equation} **Proof:**

If $x\<y$ then $\neg \text{I}(N,x,y)$ by definition, and if $x\>y$ then $\neg \text{I}(N,x,y)$ also by definition. If $x\>y$ **and** $y\>x$ then by transitivity and reflexivity, we have $\text{I}(N,x,y)$, which is a contradiction. Consequently, no more than one of the statements is true.

We keep $y$ fixed and induct on $x$. When $\text{I}(N,0,y)$ we have $0 \< y \lor \text{I}(N,0,y)$ for all $y$, which proves the base case. Next, suppose the theorem holds for $x$; now we want to prove the theorem for $S(x)$. From the trichotomy for $x$, there are three cases: $x\<y,\text{I}(N,x,y)$, and $x\>y$. If $x\>y$, then clearly $S(x) \>y$. If $\text{I}(N,x,y)$, then $S(x) \>y$ (as $S(x) \>x$ for all $x\in \mathbb{N}$). Finally, suppose $x \<y$ Then, by theorem A we have $S(x) \< y$ or $\text{I}(N,S(x),y)$, and in either case we are done. \begin{equation} \tag{$\square$} \end{equation}

The theorems that I wish to prove, can be expressed as follows in Coq.

> Lemma less\_lem (x y:N) : less x (succ y) -\> or (less x y) (I N x y).
>
> Theorem Ntrichotomy: (forall x y:N, or (less x y) (or (I N x y) (less y x))).

## Useful results

Here, I have gathered some of the results that I have defined, and proved up to this point. These are the ones that I refer to above. **This is the code that I have managed to write so far, note that most consists of definitions. **

```
(* Sigma types *)

Inductive Sigma (A:Set)(B:A -> Set) :Set :=
  Spair: forall a:A, forall b : B a,Sigma A B.

Definition E (A:Set)(B:A -> Set)
  (C: Sigma A B -> Set)
  (c: Sigma A B)
  (d: (forall x:A, forall y:B x,
      C (Spair A B x y))): C c :=

match c as c0 return (C c0) with
| Spair a b => d a b
end.

(* Binary sum type *)

Inductive sum' (A B:Set):Set :=
inl': A -> sum' A B | inr': B -> sum' A B.

Print sum'_rect.

Definition D (A B : Set)(C: sum' A B -> Set)
(c: sum' A B)
(d: (forall x:A, C (inl' A B x)))
(e: (forall y:B, C (inr' A B y))): C c :=

match c as c0 return C c0 with
| inl' x => d x
| inr' y => e y
end.

(* Three useful finite sets *)

Inductive N_0: Set :=.

Definition R_0
  (C:N_0 -> Set)
  (c: N_0): C c :=
match c as c0 return (C c0) with
end.

Inductive N_1: Set := zero_1:N_1.

Definition R_1
  (C:N_1 -> Set)
  (c: N_1)
  (d_zero: C zero_1): C c :=
match c as c0 return (C c0) with
  | zero_1 => d_zero
end.

Inductive N_2: Set := zero_2:N_2 | one_2:N_2.

Definition R_2
  (C:N_2 -> Set)
  (c: N_2)
  (d_zero: C zero_2)
  (d_one: C one_2): C c :=
match c as c0 return (C c0) with
  | zero_2 => d_zero
  | one_2  => d_one
end.

(* Natural numbers *)

Inductive N:Set :=
zero: N | succ : N -> N.

Print N.

Print N_rect.

Definition R
  (C:N -> Set)
  (d: C zero)
  (e: (forall x:N, C x -> C (succ x))):
  (forall n:N, C n) :=
fix F (n: N): C n :=
  match n as n0 return (C n0) with
  | zero => d
  | succ n0 => e n0 (F n0)
  end.

(* Boolean to truth-value converter *)

Definition Tr (c:N_2) : Set :=
match c as c0 with
  | zero_2 => N_0
  | one_2 => N_1
end.

(* Identity type *)

Inductive I (A: Set)(x: A) : A -> Set :=
r :  I A x x.

Print I_rect.

Theorem J
  (A:Set)
  (C: (forall x y:A,
              forall z: I A x y, Set))
  (d: (forall x:A, C x x (r A x)))
  (a:A)(b:A)(c:I A a b): C a b c.
induction c.
apply d.
Defined.

(* functions are extensional wrt
  identity types *)

Theorem I_I_extensionality (A B: Set)(f: A -> B):
(forall x y:A, I A x y -> I B (f x) (f y)).
Proof.
intros x y P.
induction P.
apply r.
Defined.

(* addition *)

Definition add (m n:N) : N
 := R (fun z=> N) m (fun x y => succ y) n.

(* multiplication *)

Definition mul (m n:N) : N
 := R (fun z=> N) zero (fun x y => add y m) n.

(* Axioms of Peano verified *)

Theorem P1a: (forall x: N, I N (add x zero) x).
intro x.
(* force use of definitional equality
  by applying reflexivity *)
apply r.
Defined.

Theorem P1b: (forall x y: N,
I N (add x (succ y)) (succ (add x y))).
intros.
apply r.
Defined.

Theorem P2a: (forall x: N, I N (mul x zero) zero).
intros.
apply r.
Defined.

Theorem P2b: (forall x y: N,
I N (mul x (succ y)) (add (mul x y) x)).
intros.
apply r.
Defined.

Definition pd (n: N): N :=
R (fun _=> N) zero (fun x y=> x) n.

(* alternatively
Definition pd (x: N): N :=
match x as x0 with
  | zero => zero
  | succ n0 => n0
end.
*)

Theorem P3: (forall x y:N,
I N (succ x) (succ y) -> I N x y).
intros x y p.
apply (I_I_extensionality N N pd (succ x) (succ y)).
apply p.
Defined.

Definition not (A:Set): Set:= (A -> N_0).

Definition isnonzero (n: N): N_2:=
R (fun _ => N_2) zero_2 (fun x y => one_2) n.

Theorem P4 : (forall x:N,
not (I N (succ x) zero)).
intro x.
intro p.

apply (J N (fun x y z =>
    Tr (isnonzero x) -> Tr (isnonzero y))
    (fun x => (fun t => t)) (succ x) zero)
.
apply p.
simpl.
apply zero_1.
Defined.

Theorem P5 (P:N -> Set):
P zero -> (forall x:N, P x -> P (succ x))
   -> (forall x:N, P x).
intros base step n.
apply R.
apply base.
apply step.
Defined.

(* I(A,-,-) is an equivalence relation *)

Lemma Ireflexive (A:Set): (forall x:A, I A x x).
intro x.
apply r.
Defined.

Lemma Isymmetric (A:Set): (forall x y:A, I A x y -> I A y x).
intros x y P.
induction P.
apply r.
Defined.

Lemma Itransitive (A:Set):
(forall x y z:A, I A x y -> I A y z -> I A x z).
intros x y z P Q.
induction P.
assumption.
Defined.

Lemma succ_cong : (forall m n:N, I N m n -> I N (succ m) (succ n)).
intros m n H.
induction H.
apply r.
Defined.

Lemma zeroadd: (forall n:N, I N (add zero n) n).
intro n.
induction n.
simpl.
apply r.
apply succ_cong.
auto.

Defined.

Lemma succadd: (forall m n:N, I N (add (succ m) n) (succ (add m n))).
intros.
induction n.
simpl.
apply r.
simpl.
apply succ_cong.
auto.

Defined.

Lemma commutative_add: (forall m n:N, I N (add m n) (add n m)).
intros n m; elim n.
apply zeroadd.
intros y H; elim (succadd m y).
simpl.
rewrite succadd.
apply succ_cong.
assumption.

Defined.

Lemma associative_add: (forall m n k:N,
I N (add (add m n) k) (add m (add n k))).
intros m n k.
induction k.
simpl.
apply Ireflexive.
simpl.
apply succ_cong.
assumption.
Defined.

Definition or (A B : Set):= sum' A B.

Definition less (m n: N) :=
 Sigma N (fun z => I N (add m (succ z)) n).

Lemma less_lem (x y:N) :
less x (succ y) -> or (less x y) (I N x y).
intro.
destruct H.
right.

(* Here is where I'm working right now *)

Defined.

Theorem Ntrichotomy: (forall x y:N,
or (less x y) (or (I N x y) (less y x))).

```

# Answer
> 7 votes
Coq is a bit more cruel than paper proofs: when you write "and we are done" or "clearly" in a paper proof, there is often much more to do to convince Coq.

Now I did a little clean up of your code, while trying to keep it in the same spirit. You can find it here.

Several remarks:

1. I used built in datatypes and definitions where I thought it wouldn't hurt your intent. Note that if I had used built-in equality instead of `identity` and the built in "less-than" relation, proofs would have been much easier, as many of your lemmas are in the database of known theorems, which are checked at each call of

```
auto with arith.

```
2. I used some tactics you're probably not aware of, but a "real" Coq super-user would have much more powerful tactics at hand and written her own tactics to simplify the job. I always recommend CPDT as the place to learn about using tactics in a powerful manner.
3. I used notations and tabbing to improve readability and built-in constructs like matching and the `induction` tactic to make things easier to prove and re-factor. In particular, your definition of `less` was hard to work with, you can see how I slightly modified it from $$ \exists x,\ m + (x+1) = n $$ to the equivalent (but easier to use) $$ \exists x,\ (x + m)+1 = n$$ this kind of "definition tweaking" happens a **lot** in formal proofs.
4. While you may get answers to these kinds of questions here, I highly recommend you submit your work to Coq-Club which was created with the express purpose of answering these kinds of questions.

# Answer
> 4 votes
Cody's answer is excellent, and fulfils your question about translating your proof to Coq. As a complement to that, I wanted to add the same results, but proven using a different route, mainly as an illustration of some bits of Coq and to demonstrate what you can prove syntactically with very little additional work. This is not a claim however that this is the shortest route - just a different one. The proofs only include one additional helper lemma, and rely only on basic definitions, I don't introduce addition, multiplication or any of their properties, or functional extensionality, and the only Peano axioms are a simple form of a \<= b -\> a+c \<= b+c in the helper lemma (just for c=1) and structural induction, which comes with inductive types for free anyway.

Like Cody, where I thought it made no difference, I used predefined types etc., so before the proof, I'll describe those:

* I used the built in nat type for natural numbers, which has (up to precise naming) the same definition as yours:

> Inductive nat : Set := O : nat | S : nat -\> nat

* I used the built in le and lt for less than or equal and less than respectively, which have notational shorthands "\<=" and "\<" for readability. They are defined:

> Inductive le : nat -\> nat -\> Prop :=
> | le\_n : forall n, le n n
> | le\_S : forall n m, (le n m) -\> (le n (S m)).

and

> Definition lt (n m:nat) := le (S n) m.

* The built in eq (shorthand "=") is syntactic equality and works the same as your "I", with one constructor that just says anything is equal to itself. The symmetric and transitive properties are easy proofs from there, but we won't need them in this case. The definition for eq below has the notation built into it.

> Inductive eq (A : Type) (x : A) : A -\> Prop := eq\_refl : x = x

* Lastly, I've used the propositional or (shorthand "\\/" - which is backslash forwardslash), which has two constructors, basically that either you have evidence for the left argument, or the right argument. Coq also has some shorthand tactics, left and right, which just mean "apply or\_introl" and "apply or\_intror" respectively.

> Inductive or (A B : Prop) : Prop :=
> or\_introl : A -\> A / B | or\_intror : B -\> A / B

What now follows are my proofs, in principle, if markup doesn't get in the way, you should be able to just cut and past this into a Coq .v file and it will work. I've included comments to note interesting bits, but they are in (\* \*) delimiters, so you shouldn't have to remove them.

```
Theorem lt_or_eq: forall (n m : nat),
  n < S m -> n < m \/ n = m.
Proof.
(*
  This proof is just a case analysis on n and m, whether they're zero or
  a successor of something.
*)
destruct n as [|n']; destruct m as [|m'].

(*n = 0, m = 0*)
intros.
  right. reflexivity.

(*n = 0, m = S m'*)
intros H.
  inversion H.
  inversion H1.
  left. unfold lt. constructor.
  (*The constructor tactic tries to match the goal to a constructor
    that's in the environment.*)
  left. unfold lt. constructor. assumption.
  (*Assumption tries to match the goal to something that's in the
    current context*)

(*n = S n', m = 0
  This case is false, so we can invert our way out of it.*)
intros.
  inversion H. inversion H1.

(*n = S n', m = S m'*)
intros.
  inversion H.
    right. reflexivity.
    left. unfold lt. assumption.
Qed.

(*
  The following lemma with be useful in the proof of the trichotomy theorem,
  it's pretty obviously true, and easy to prove. The interesting part for
  anyone relatively new to Coq is that the induction is done on the
  hypothesis "a <= b", rather than on either a or b.
*)
Lemma a_le_b_implies_Sa_le_Sb: forall a b, a <= b -> S a <= S b.
Proof.
  intros a b Hyp.
  induction Hyp.
  constructor.
  constructor.
  apply IHHyp.
Qed.

(*
  The proof of the trichotomy theorem is a little more involved than the
  last one but again we don't use anything particularly tricky.
  Other than the helper lemma above, we don't use anything other than the
  definitions.

  The proof proceeds by induction on n, then induction on m.  My personal
  feeling is that this can probably be shortened.
*)
Theorem trich: forall (n m : nat),
  n < m \/ n = m \/ m < n.
Proof.
  induction n.
    induction m.
      right. left. reflexivity.
        inversion IHm.
          left. unfold lt. constructor. unfold lt in H. assumption.
          inversion H.
          left. unfold lt. subst. constructor.
          inversion H0.
    induction m.
      assert (n < 0 \/ n = 0 \/ 0 < n).
      apply IHn.
      inversion H.
      inversion H0.
      inversion H0.
      right. right. subst. unfold lt. constructor.
      right. right. unfold lt. constructor. assumption.
      inversion IHm. unfold lt in H.
      left. unfold lt. constructor. assumption.
      inversion H; subst.
      left. unfold lt. constructor.
      inversion H0.
      right. left. reflexivity.
      right. right. apply lt_or_eq in H0.

      inversion H0.
      apply a_le_b_implies_Sa_le_Sb. assumption.
      subst. unfold lt. apply a_le_b_implies_Sa_le_Sb. assumption.
Qed.

(*
  The following is just to show what can be done with some of the tactics
  The omega tactic implements a Pressburger arithmetic solver, so anything
  with natural numbers, plus, multiplication by constants, and basic logic
  can just be solved. Not very interesting for practicing Coq, but cool to
  know.
*)

Require Import Omega.

Example trich' : forall (n m : nat),
  n < m \/ n = m \/ m < n.
Proof.
  intros.
  omega.
Qed.

```

---
Tags: automated-theorem-proving, proof-assistants, mathematical-programming, coq
---


title: Is Dominosa NP-Hard?

text:
# Question
Title: Is Dominosa NP-Hard?
Dominosa is a relatively new puzzle game. It is played on an $(n+1)\times(n+2)$ grid. Before the game begins, the domino bones $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$ are placed on the grid (constituting a perfect tiling). In the next step, the domino bones are hidden, leaving only the numbers revealed. The purpose of the game is to recover the original arrangement of the domino bones. You can play the game here: http://www.puzzle-dominosa.com/:

Rules:

> The rules are simple. You have to find the location of all the dominoes on the grid. A domino is a pair of numbers. You can only have one of each pair.

I have some polynomial algorithms that solve a relatively small part of the puzzle. I could also show that typical Dominosa grids have at least $2^{\frac{n}{2}+o\left(n\right)}$ solutions.

Is Dominosa NP-Hard?

# Answer
Note: This is a continuation and revision of my other answer.

# **Problems with the reduction**

Recall the decision problem:

> Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables.

But:

> * Our reduction requires a *lot* of unique variables, much more than $\mathcal O(n)$.
> * Furthermore, our wires are open ended, which leads to:
>     + **How do we know we can tile the open areas?**

To solve the first problem, we artificially make the game-board much larger; essentially we make $n$ equal to the number of variables we actually require, then create a grid of size $(n+1)\times(n+2)$, and place our grid in the lower left corner. This will lead to a quadratic blowup.

For the second problem, we must rethink our gadgets a bit.

It can seem a little daunting to prove that we can successfully tile the rest of the board according to the rule. So we start off with the same strategy one would use to actually generate game-boards of size $(n+1)\times(n+2)$:

> *First* we generate a set of all possible tiles. All of these tiles will have to be placed on the board. *Then* we remove the tiles, and leave behind their squares.

However, our gadgets don't guarantee a particular set of tiles will be placed; the tiles placed depend on the state. So we must carefully modify the gadgets to *guarantee* particular tiles will be removed, no matter which state is chosen.

Let's go over our gadgets then.

The wire and clause-gate are problematic for two reasons.

1. We don't know that the squares surrounding a wire or clause-gate can be tiled correctly; after all, some wires can be pushed to the left, others to the right, and tiling the remaining white-space squares becomes non-trivial. We'll refer to this problem as the "flow" problem.
2. There is no way of knowing *which* tiles to remove from the tile-set; in one state, one set of squares, in the wire or clause-gate, will be tiled, in another state, an entirely different set of squares will be tiled.

To solve these issues:

* First, we generate a set of all possible tiles. All of these tiles will have to be placed on the board; as we place them on the board, we will remove the tile from the set. Though we might not at first know $n$, since we have yet to fully describe the formulation, we can add all the new tile possibilities as we increment $n$, as needed. All of the tiles we remove from this set must guaranteed be placeable (at least, be guaranteed to be placeable if the formula is satisfiable). We call removing a tile from the tile-set, to "discharge" the tile from the tile-set, as in to discharge our obligation to place it on the game-board.
* We must carefully design the gadgets to *guarantee* particular tiles will be removed, no matter which state is chosen.
* We must close our gadgets, so that they don't push tiles all around the board depending on their state; rather all of their states must only take up a particular well defined area.
    + Alternatively, all of their states must *be guaranteed to be **able*** to take up a well defined area; this guarantees a satisfiable tiling, but does not guarantee that a particular tiling will occur. This is the same way a Dominosa game is made:
        - First the tiles are generated into a set;
        - Then the tiles are placed down in a random configuration,
        - As each tile is placed, it is removed from the tile-set.
        - Then the tiles are removed from the board, leaving behind their squares.
        - This does not guarantee that the intended configuration *will* be chosen,
        - Rather, it guarantees that the intended configuration is *able* to be chosen, and thus a solution exists. We can do the same thing here.
* After placing all the gadgets of the formulation, instead of placing unique ${\star}$ squares by default, i.e. on all "whitespace", we make sure the whitespace is a rectangular area with one even dimension, or break down the whitespace into rectangles with one even dimension, and we simply tile the whitespace with the remaining tiles in the tile-set.
* After placing all the tiles from the set, we know everything is placeable.
    + Some tiles will be obviously placeable, such as those in walls, others will be placeable only iff the formula is satisfiable, due to the nature of the relationships between the gadgets.
* Then we remove the tiles, and leave behind their squares.

Let's go over our gadgets then.

### Forcing gadget

We can make an arbitrary number of building blocks by making sure they each can't be paired with themselves.

For example, let us say we want to force a $\mathbf{({1}{\star},{1}{\star})}$ tile, so that we can use $\mathbf{1}{\star}$ as a building block. (note, ${1}{\star}$ is an arbitrary variable, which we want to force as pair to itself, not necessarily a building block as we used the $1$ value previously)

To guarantee that our $\mathbf {1}{\star}$-building-block reserves $\mathbf{({1}{\star},{1}{\star})}$, we will place it against the bottom wall in the following configuration: we will place the reserved number, let us call it $\mathbf{1}{\star}$ against the wall like an up-tack (shaped like $\bot$); $3$ against the wall, and one in the 2nd row in the middle. Then we will place another two numbers, let us call them ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$; these are unique to this gadget. We place these on top of the left and right $\mathbf{1}{\star}$.

Illustrated below, shared black border is the bottom of the game-board, description from left-to-right.

* Configuration of the gadget. Each ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ here are unique to this gadget.
* The 3 possible states of tiling the center $\mathbf{1}{\star}$.

After doing this, we can guarantee that our gadget *can* be tiled with a specific set of tiles, while guaranteeing that our gadget *must* force the $\mathbf{({1}{\star},{1}{\star})}$ pair.

* We know that $\mathbf{({1}{\star},{1}{\star})}$ must occur, because all 3 possible tiling states of the lower middle $\mathbf{1}{\star}$, tile as $\mathbf{({1}{\star},{1}{\star})}$, as illustrated in the figure on the right, above.
* The remaining tiles *can* be tiled as $({1}{\star},{2}{\star})$ and $({1}{\star},{3}{\star})$, covering the gadget. Thus, we can remove those tiles from our global tile-set. Illustrated below.

Description, left to right:

* **Left, top:** Left state, **Left, bottom:** A valid tiling of the remaining squares.
* **Middle, top:** Middle state, **Middle, bottom:** A valid tiling of the remaining squares.
* **Right, top:** Right state, **Right, bottom:** A valid tiling of the remaining squares.

Note, that the tiling of the remaining squares isn't *forced*, since they can tile with nearby neighbors instead of $\mathbf{1}{\star}$, but since it is a valid tiling of the game-board in all of the states, we can remove them from the tile-set, and assume they will be tiled in exactly that way. Since we know there is a valid possible tiling, we have at least one possible tiling of the game-board, if the formula is satisfiable. Though there is no guarantee that these will be tiled this way, there is a guarantee that the $\mathbf{({1}{\star},{1}{\star})}$ tile will be forced.

**Note:** if you aren't satisfied with this, or are confused by the difference of "being able to tile" vs. "being forced to tile", you can simply place a wall around the $3\times 2$ gadget, the same way we make a $3\times 2$ wall below for the clause-gadget.

**This gadget is not closed, because it doesn't need to be (but you can if you want to).** It doesn't need to be, because it has a feasible configuration, which we can remove from the tile-set. Although it might be possible to do a different configuration, this does not affect the satisfiability of the problem.

**The following tiles are guaranteed to be to be tiled (thus can be removed from the tile-set):** $\mathbf{({1}{\star},{1}{\star})}$

**The following tiles are guaranteed to be *able* to be tiled (thus can be removed from the tile-set):** $({1}{\star},{2}{\star}), ({1}{\star},{3}{\star})$

If you choose to close this gadget with a wall, then $({1}{\star},{2}{\star}), ({1}{\star},{3}{\star})$ will also be guaranteed to be covered.

## New Wire and Clause gates

Because of the problems of flowing, and the emptying the tile-set, we need to redesign the wire a bit.

One way to solve the flow problem, is to make the wire a circuit, instead of just simple left-right states; that is, it would be circular instead of a line, and therefore if the top part of the circle is pushed right, the bottom will be pushed left. This solves the flow problem.

Following this route, we can change the wire and clause gate to solve both problems.

### Reserving $\mathcal T$ and $\mathcal F$

Let us introduce two new universal values, $\mathcal T$ and $\mathcal F$. These two values are universal; actual values in the grid, such as square-values $2$ and $3$ (since by convention, we reserved $1$ as a building block for walls), or whatever you choose. They represent true and false, respectively.

We force-reserve the tiles $(\mathcal T, \mathcal F)$, $(\mathcal T, \mathcal T)$, $(\mathcal F, \mathcal F)$, as follows; illustration below, description from left to right:

* We use the same scheme as forcing any $\mathbf{({1}{\star},{1}{\star})}$ tile, using $\mathcal T$ as $\mathbf{1}{\star}$. Each ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ here are unique to this gadget.
* We use the same scheme as forcing any $\mathbf{({1}{\star},{1}{\star})}$ tile, using $\mathcal F$ as $\mathbf{1}{\star}$ Each ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ here are unique to this gadget.
* We use the same scheme as forcing a $\mathbf{({1}{\star},{1}{\star})}$ tile, using $\mathcal F$ as $\mathbf{1}{\star}$ in the center, and using $\mathcal T$ in the other locations of the up-tack. This forces $(\mathcal F, \mathcal T)$ to tile. ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ are able to tile with $\mathcal T$, so we remove them from the tile-set. Each ${\mathbf 2}{\star}$ and ${\mathbf 3}{\star}$ here are unique to this gadget.

### Wire

Each wire will start and end with a value, let us call it ${A}{\star}$, which is unique the to wire. For each clause the wire participates in, the wire will have two wire-values, ${x}{\star}$, and ${x'}{\star}$, which are unique to each wire, and participate in the same clause. Illustration below, with description from left to right.

* A wire that participates in one clause. The wire has a height of $2$, and has a length of $2\*p+3$, where $p$ is the number of clauses the wire participates in. The wire is padded by two ${A}{\star}$ squares on the left, and two on the right. It is, of course, surrounded by a wall on all sides, indicated by the blue outline. Note, that the ${1}{\star}$ is unique to this wire, and will only be used in the wire, and the clause it participates in.

Illustrated below are the two states, descriptions from left to right.

* A wire that participates in one clause, in the true state. The wire is considered true, when the ${x}{\star}$ squares are paired with a $\mathcal T$ squares, and the ${x'}{\star}$ squares are paired with $\mathcal F$ squares. It is considered false in the other state, where the tiling is reversed. Note how the tiling is forced once the ${A}{\star}$ tile is selected: $(\mathcal T,\mathcal F)$ are already forced earlier, thus the rest of the tiles must be horizontal.
* The same wire in the false state.

When participating in more clauses, there are more value ${x}{\star}$, and ${x'}{\star}$, one pair for each clause the wire participates in. They alternate being on top and bottom, as does the $\mathcal T$ and $\mathcal F$ squares that separate each ${x}{\star}, {x'}{\star}$ pair.

The two corresponding states.

**This gadget is closed**, thus there is no "flow problem".

**Note how in either state, we collect the following tiles, no matter the state:** $({A}{\star},{A}{\star})$, $({A}{\star},\mathcal T)$, $({A}{\star},\mathcal F)$.

There are some tiles however, that we are unsure of; in one state we can remove $({1}{\star}, \mathcal T), ({1'}{\star},\mathcal F), ({2}{\star},\mathcal T), ({2'}{\star},\mathcal F) ...$ from the tile-set, while in another state we can remove $({1}{\star}, \mathcal F), ({1'}{\star},\mathcal T), ({2}{\star},\mathcal F), ({2'}{\star},\mathcal T) ...$ from the tile-set, so which tiles can we actually remove? The answer is: the clause gate has the same problem, but with the opposite set of tiles. It will always collect the remaining, opposite, and uncollected tiles, as we will see in the next section. Since each of these is paired with a clause gate, we will be able to remove them both.

### Clause

Next we will create the first iteration of the new clause gate. It consists of a $2\times 3$ gadget, enclosed by walls. Inside the gadget, we place one $\mathcal F$ in the top-center, and two $\mathcal T$ squares in the lower corners; one in the lower-left, and one in the lower-right. The remaining squares will be values representing wire-variables of three different wires. Let us call these ${a}{\star}, {b}{\star},$ and ${c}{\star}$. The $\mathcal F$ will be forced to pair with one of the wire-variables, and the remaining wire-variables will pair with the $\mathcal T$ values. Illustrations below, descriptions from left to right.

* **Left:** The configuration for the first iteration of the new clause-gate.
* **Right** The three possible states of the $\mathcal F$ tiling.

These three states leads to three possible tilings. Illustration below, descriptions from left to right.

* **Left, top**: $\mathcal F$ tiled left, **Left, bottom:** Tiling the remaining squares.
* **Middle, top**: $\mathcal F$ tiled right, **Middle, bottom:** Tiling the remaining squares.
* **Right, top**: $\mathcal F$ tiled down, **Right, bottom:** Tiling the remaining squares.

Since the $\mathcal F$ will be paired with one of the wire-variables **in the clause**, that wire-variable can no longer be paired with $\mathcal F$ **in the wire**; thus forcing the wire to true. Conversely, the remaining wire-variables that tile with $\mathcal T$ will be forced to tile with $\mathcal F$ within their wires. This is exactly the same constraints as a $\rm 1\text{-in-}3\text{-}S{\small AT}$ clause.

Note, ${a}{\star}, {b}{\star},$ and ${c}{\star}$ are wire-variables, but they could each refer to an ${x}{\star}$ or an ${x'}{\star}$ wire-variable; using an ${x'}{\star}$ is essentially negating the wire-variable.

One addition: to discharge the obligation of knowing which tiles can be removed from the tile-set, we have to "double and contrapositive" the clause. What I mean by this, is to make another $3\times 2$ gadget, with $3$ additional variables representing the negations of ${a}{\star}, {b}{\star},$ and ${c}{\star}$. Let us call these ${a'}{\star}, {b'}{\star},$ and ${c'}{\star}$. These *must* be the negated variable-wire values of ${a}{\star}, {b}{\star},$ and ${c}{\star}$. This $3\times 2$ gadget is different, in that it will have a $\mathcal T$ at the center, and two $\mathcal F$ values at the corners; exactly the opposite of the clause gadget described thus far. By "doubling" the clause like this, we re-add the same constraints as the gadget described above. However, we also discharge all the combinations of $(\mathcal T, {x}{\star}), (\mathcal T, {x'}{\star}), (\mathcal F, {x}{\star}), (\mathcal F, {x'}{\star})$ from the tile-set, for each variable (and thus for ${a}{\star}, {b}{\star},$ and ${c}{\star}$ as well, because they are after all, wire-variables). Illustrated below, descriptions from left to right.

* A "double and contrapositive" clause. The bottom section is the clause described above; the top section is the newly described contrapositive clause. The new clause has exactly the same logical constraints; it is the contrapositive of the bottom clause. Together, these combined gadgets and the wire discharge all of the combinations of $(\mathcal T, {x}{\star}), (\mathcal F, {x}{\star}), (\mathcal T, {x'}{\star}), (\mathcal F, {x'}{\star})$ from the tile-set, for each wire-variable participating in the clause.
* The blue line in the middle of the left-most figure is there for ease-of-viewing; in reality it can be removed without allowing any more states.

So, let us take an example, to show that all the tiles get discharged as promised. Illustrated below, description from left to right.

* Figure of a wire participating in a single clause; a state is chosen for the clause. Here, we are using ${1}{\star}={b}{\star}$, while ${a}{\star}$ and ${b}{\star}$ are representing other wire-values in this clause.
* For the given state in the clause, the ${1}{\star}$ value is forced to be paired with the neighboring $\mathcal T$.
* This causes the wire to be forced to be true-valued (you can tell as the positive variable of the wire is forced to pair with the $\mathcal T$, and the negative variable is forced to pair with the $\mathcal F$, as explained above).
* This forces the ${1'}{\star}$ in the contrapositive clause (the upper section of the clause) to be paired with $\mathcal T$ within the clause. Now if you look at the wire, every tile within the wire is guaranteed to be discharged: either discharged in the wire itself, or in the corresponding clause-gadget. In this state, we have the tiles, $({A}{\star},{A}{\star})$, $({A}{\star},\mathcal T)$, $({A}{\star},\mathcal F)$, $({1}{\star},\mathcal T)$, $({1}{\star},\mathcal F)$, $({1'}{\star},\mathcal F)$, and $({1'}{\star},\mathcal T)$.

Trying the other state, we get the illustration below, description from left to right.

* The clause is in the other state, tiling $({1}{\star},\mathcal T$ in one of two ways.
* Therefore, $({1}{\star},\mathcal F$ is forced on the wire,
* Leading the rest of the wire to tile correspondingly, and value the wire as false.
* Finally, in the contrapositive/upper section of the clause-gadget, $({1'}{\star},\mathcal F)$ must tile, because $({1'}{\star},\mathcal T)$ is taken in the wire. In this state, we have the tiles, $({A}{\star},{A}{\star})$, $({A}{\star},\mathcal T)$, $({A}{\star},\mathcal F)$, $({1}{\star},\mathcal T)$, $({1}{\star},\mathcal F)$, $({1'}{\star},\mathcal F)$, and $({1'}{\star},\mathcal T)$. **These are the same tiles discharged as in the other state**.

Thus in either state, we discharge the same tiles. Therefore, the wire and clause together successfully discharge specific tiles iff there is a satisfying assignment.

**This gadget is closed**, so there won't be a flow problem. **The clause-gadget *together with the wire gadget* are guaranteed to always discharge the same tile-pair values**, and thus we can discharge these even if we don't know which way it will tile.

Now all of our gadgets fulfill the criteria.

## Formulation

In our final formulation, we create three rows of gadgets, each separated by a horizontal wall.

* On the bottom, we place the forcing-gadgets, which are two tiles tall. We need a forcing gadget for the building block, and for combinations of $\mathcal T$ and $\mathcal F$. We place the forcing gadgets directly next to each-other.
* In the middle row, we place the wire gadgets, horizontally, which are two tiles tall. The wire gadgets should be separated from each-other with a vertical wall.
* In the top row, we place clause gadgets, which are four tiles tall. The clause gadgets should be separated from each-other by a vertical wall.

Illustrations follow, descriptions above each figure. **Click images for full resolution.** Source code to reproduce/generate the images is listed at the bottom of the page.

Using the formula $\Phi(\mathbf x)= (x\_1,\neg x\_2, x\_3) \wedge (x\_2,\neg x\_3,x\_4) \wedge (x\_1,x\_2,\neg x\_4)$ as an example, we have a satisfying solution $(\neg x\_1,x\_2,x\_3,\neg x\_4)$ as a witness.

First we start with the horizontal walls separating the rows of gadgets. We show the squares, and the pairs that are forced to tile within the walls.

Next, we show the gadgets. The blue outline represents the borders of the gadgets; dashed blue for the forcing-gadgets, since they will not be surrounded by walls. Note the line in the middle of the clause gadget is not surrounded by a wall; it is there for ease-of-viewing; taking the line away does not allow any more states to occur in the clause, as explained above, but we show the blue line for this demonstration. ***Note:** that we use square-names to give the numbers semantic readability, when applicable. Each name represents a numeric value.*

Here we fill in the vertical walls.

Here we fill in the witness solution; i.e this is the tiling solution if using the SAT solution to generate it.

Next we tile the filler-area; the rest of the board, as large as needed, for as large as $n$ is required to tile thus-far. Thus we discharge the remaining pairs in the tile-set. The dashed lines here represent a valid-but-not-forced tiling; there might be another way of tiling these. Here we show the lower-left corner.

Here we fill in the remaining squares with a trivial valid tiling.

Here we show the lower right corner of the grid.

Here we show the upper right corner of the grid. Note how the vertical tiles no longer fit; so we tile the top row horizontally, if necessary.

And finally the top-left corner.

Generating the entire game-board at once via TeX fails with out-of-memory errors from pdflatex, so if you want to see it, you would have to generate clips and patch them together. **Be sure to check out the notebook viewer.**

---

## TikZ sources

Game generator:

* graphtex.py

Converts TeX to svg, using pdflatex, pdfcairo (poppler), and rsvg-convert (libsvg)
* dominosa.py

Contains the conversion logic, game-solution verification, and drawing logic
* dominosa\_demo.py

An executable demo that generates the images used in the answer above. Dumps images to the current-working-directory.
* dominosa\_demo.ipynb

An ipython demo that generates the images used in the answer above.
> 9 votes

# Answer
## ${\rm D{\small OMINOSA}}$ is NP-hard

---

Playing the game is an optimization problem; finding a valid domino tiling such that it covers all the squares. The decision version of this problem is:

> Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

Obviously, the optimization problem, the problem of actually finding a solution to the game is at least as hard, or harder, than the decision problem.

We will convert a $1\text{-}3\text{-in-}{\rm S{\small AT}}$ formula to a corresponding grid, that will only be coverable iff there is a satisfiable assignment to the formula. Furthermore, the covering can actually be used to recover the satisfying assignment.

Therefore, if the construction presented is correct, and one could solve a game in polynomial time on a DTM, then it would imply ${\rm P=NP}$. This implies ${\rm D {\small OMINOSA}}$ is NP-hard.

### Reduction from $1\text{-}3\text{-in-}{\rm S{\small AT}}$ to ${\rm D {\small OMINOSA}}$

### Introduction

Most of the $3\text{-}{\rm S{\small AT}}$ problems/variants have a pretty good correspondence to ${\rm C{\small IRCUIT}S{\small AT}}$. It can be important to think of the problems in parallel; as they are related to each-other, almost anything in one problem can be related to in the other.

${\rm C{\small IRCUIT}S{\small AT}}$ has a planar variant, to which it reduces, called ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$. This conversion is very elegant, and basically allows you to take any planar embedding, find the remaining crossing wires, and use a "gadget" to let the wires cross via a planar "gate" (collection of gadgets, with input and output wires).

Conveniently, most of the $3\text{-}{\rm S{\small AT}}$ variants also have reductions to planar variants, which parallel ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$, and are very related; easily reducible from one to another, and easy to reason about. So whenever I come to a planar problem that might be NP-hard, I think in terms of the planar variants of $3\text{-}{\rm S{\small AT}}$, and their parallels in ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$.

The planar variants are important to know, because they make help make reductions to planar/geometric problems, like Euclidean TSP (incidentally a pretty rare reduction to find and learn). Thus, there is ${\rm P{\small LANAR}}\text{-}3\text{-}{\rm S{\small AT}}$, and a parellel, ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$, to aid in such reductions.

Other $3\text{-}{\rm S{\small AT}}$ variants are important to know because some of them are weaker; that is, seemingly "easier", yet still NP-complete. They *seem* easier to solve at first glance - and they are much simpler - yet are *still* NP-complete. NP-complete, but simpler; and therefore easier to make reductions to, in many cases.

For example, there is $1\text{-in-}3\text{-}{\rm S{\small AT}}$. For some problems, you can easily make an exactly $1\text{-in-}3$ gadget, while making "at least 1 in 3", like the standard $3\text{-}{\rm S{\small AT}}$ uses, would be non-obvious and make for huge constructions.

Another example is ${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$. Monotone makes things a lot simpler when you have a construction that can't easily negate values.

Even more amazing is that ${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$ has a planar variant: ${\rm P{\small LANAR}}\text{-}{\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$! So this makes things a lot easier; you don't have to cross "wires" (remember, there are parallels in ${\rm C{\small IRCUIT}S{\small AT}}$ to these), and trust me, while crossing gadgets are fun to make, they tend to be very non-obvious and difficult.

$$ \begin{array}{c|c|c|ccc} &&&&\hspace{1em}&\hline\\ {\rm\mathbf{P{\small ROBLEM}}} &\scriptsize{{\rm\mathbf{MONOTONE}}} &\scriptsize{{\rm\mathbf{PLANAR}}} &\scriptsize{{\rm\mathbf{1\text{-in-}3}}} &&{\rm\mathbf{NP\text{-}hard}} \\ \hline\\ {\rm\mathbf{3\text{-} S{\small AT}}} & \text{No} & \text{No} & \text{No} && \text{Yes}\\ \hline\\ {\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}} & \text{Yes} & \text{No} & \text{No} && {\text{No}}^1\\ {\rm\mathbf{P{\small LANAR}\text{-}3\text{-} S{\small AT}}} & \text{No} & \text{Yes} & \text{No} && {\text{Yes}}^2\\ {\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}} & \text{No} & \text{No} & \text{Yes} && {\text{Yes}}^3\\ \hline\\ \genfrac{}{}{0}{1} {\rm\mathbf{P{\small LANAR}}} {\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}} & \text{No} & \text{Yes} & \text{Yes} && {\text{Yes}}^4\\\\ \genfrac{}{}{0}{1} {{\rm\mathbf{M{\small ONOTONE}\text{-} }}} {{\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}} & \text{Yes} & \text{No} & \text{Yes} && {\text{Yes}}^5\\\\ \genfrac{}{}{0}{1} {{\rm\mathbf{P{\small LANAR}\text{-}}}} {{\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}}} & \text{Yes} & \text{Yes} & \text{No} && {\text{Yes!}}^6\\ \hline\\ \genfrac{}{}{0}{1} {{\rm\mathbf{P{\small LANAR}\text{-}M{\small ONOTONE}\text{-} }}} {{\rm\mathbf{1\text{-in-}3\text{-}S{\small AT}}}} & \text{Yes} & \text{Yes} & \text{Yes} && {\text{Yes}}^7\\ \end{array} $$

1. Pure literal elimination
2. Schaefer's dichotomy theorem
3. The Problem of Compatible Representatives
4. Minimum Weight Triangulation is NP-Hard
5. Schaefer's dichotomy theorem
6. Finding Perfect Auto-Partitions is NP-hard
7. Optimal Binary Space Partitions in the Plane

---

One way to start with a reduction, is to try to find "gadgets" that resemble wires, and a gadget that resembles a clause of one of the $3\text{-}{\rm S{\small AT}}$ variants. As a bonus, many of the variants are planar, we can probably get away without crossing wires.

What is a "gadget"? A gadget is some construction in the problem, that is helpful as a building block to build gates/wires/clauses. Some gadgets will have a restricted set of states; for example, a gadget with two states can be used as a variable; one state is "true" and the other is "false". A gadget with two states, that can be "long", can bend, and split, is useful as a wire - if it can interact with a variable, and become constrained to extend the state of the variable to another location. A gadget with exactly three states can perhaps be used as a clause; if it can be used to constrain "one of three" wires via each one of its three states. Similarly, one might want all sorts of logic gates, like a not-gadget, an or-gadget, an xor-gadget etc; where you can have some sort of constraint via the gadget that relates 2 or 3 wires in such a way.

### **A Building-block**

* First, let's reserve a number, for example, $\mathbf 1$, on the board. We will make $\mathbf 1$ a building block for everything else.
* We will use a corner to make sure that $\mathbf 1$ can never connect to another $\mathbf 1$, except in this corner, where it must.
* Below (in the three figures) is the corner, and how we place the $\mathbf 1$s there.
* We will use the $\star$ to indicate unique values in all the grid, in all the diagrams.
* In fact, we will cover our grid with $\star$ values before overlaying them with important values; therefore, by default cover everything with $\star$ values.

As you can see, by placing the $3$ $\mathbf{1}$s the pair $\mathbf{(1,1)}$ *must* be used up in this configuration; it must use one of the dashed-tiles. Now $\mathbf{(1,1)}$ can never happen elsewhere in the board, which is what we need.

There are alternate ways of reserving a number, either against the wall with $4$ of them, or in the middle of nowhere, with $5$ of them in a cross. Any way is fine, as long as $\mathbf{(1,1)}$ is forced.

### **A Wall**

Now, it would be very useful to be able to make "walls" and "corners" all over the place, not just at the sides of the grid. Look what happens if we line up pairs of ones in a line; the one's have no choice but to pair with their neighbors, making a "wall" of width $4$.

Images below, from left to right:

1. A line of pairs of $\mathbf 1$s.
2. The only possible tiling of that $\mathbf 1$-square.
3. The only possible tiling of (almost) all the $\mathbf 1$s in the line.
4. The wall line, drawn for emphasis.

### **An initial attempt at a wire**

Now, by placing two "walls" opposite each-other, and leaving a space of $\mathbf 1$ between the walls, perhaps we can come up with a "wire"-like gadget.

Showing only the wall-borders, this is what we get in the figures below (left to right):

* Placing two walls opposite each-other.
* Putting unique numbers inside.
* **Rightmost two:** Two possible states of the wire.

How it works:

> There cannot be any holes in the tube/wire, therefore, if the the tiles are shifted up, then they *all* must be shifted up, all along the tube; if they are shifted down, it will "suck" down all of them. Thus, we can send a "signal" from one side of the wire to the other; in other words, propagate a value.

Thus, now we can propagate a value across long distances!

Remaining limitations are:

* We cannot bend a wire,
* We cannot split a wire,
* We cannot cross wires,
* We might have annoying layout issues because we must be careful about wire-length parity.

### **Bending a Wire**, Part 1: Wall Below

Next problem is, we need to be able to bend a wire, not just go straight ...

So. We will break the bending part down into two parts; the upper part and the lower part. First the lower part. **Ignore the upper part of the bend, we will do that later.**

The figures below show a bit of a problem with bending; the top of the wire is "loose", it seems difficult to make a wall that turns a sharp 90 degrees.

Left to right:

* The top of a wire is "loose".
* What happens if we try to bend it; we want to wire to be in between the blue lines. Again, **Ignore the upper part of the bend, we will do that later.**
* As you can see, the top $\mathbf 1$s are loose, they can tile along the wall, or *through the wire*! This is no good.

One solution is as follows:

* Pick a $\mathbf{(x,1)}$ pair near the bend. Take the value of that $\mathbf x$ square, let us name it $\mathbf{ q \star}$; this means the number is unique in the entire grid, just like $\mathbf \star$, and is reused once, here *in this bend **only***. Because this $\mathbf x$ is paired with a $\mathbf 1$, it cannot be paired with a $\mathbf 1$ again. Therefore, we place it right on top of the rightmost-topmost $\mathbf 1$. Now, we can clearly see, the only option remaining to pair for that $\mathbf 1$ is to its right, and thus it will solidify the wall.

Illustration below, description from left to right:

* The situation with the problem.
* Pick a square, let $\mathbf{q \star}$ be the square value of any square in the bend (of course not $\mathbf 1$s though).
* The two togglings of the rightmost-topmost $\mathbf 1$ tilings; this time, only one of them is valid.

However, how can we be sure this $\mathbf {{q}{\star}}$ won't ruin the wire? Below you can see the states of the wire, and that the $\mathbf {{q}{\star}}$ will not hamper with it.

From left to right:

* The current construction.
* **Two rightmost figures:** The states of the wire; empirically, they are not hampered by the introduction of $\mathbf {{q}{\star}}$.

Now we still have a loose $\mathbf 1$ on top; the leftmost-topmost-$\mathbf 1$.

We will do the same thing; pick a pair $\mathbf{({r}{\star},1)}$ that is already paired in the bend-tiles, and place $\mathbf{r}{\star}$ on top of the leftmost-topmost-$\mathbf 1$.

Illustration below, left to right:

* Our current construction.
* The problem: leftmost-topmost-$\mathbf 1$ can pair with a number in the wire, *or* with the wall; we *want* it to *only* pair with the wall.
* Choosing an $\mathbf{r}{\star}$, and using the same number on top of the leftmost-topmost-$\mathbf 1$.

And we finally get our lower bend. Illustration below, descriptions, from left to right:

* **Left:** Our final construction for a bend.
* **Right:** How to continue the wire to the left.

### **Bending a Wire**, Part 2: Wall Above

The walls to make the top corner of the bend are much simpler. You simple align a vertical wall with a horizontal wall. Illustration below, description from left to right:

* The wire-bend we want to make.
* Place the vertical section of the wall squares down.
* Tiling the squares of the vertical-wall.
* Placement and tiling of the horizontal wall; it can meet the vertical wall, and form a corner.

Now you should be convinced that we can place and bend wires. We still can't split or cross wires though, more on that later.

Remaining limitations are:

* ~~We cannot bend a wire,~~
* We cannot split a wire,
* We cannot cross wires,
* We might have annoying layout issues because we must be careful about wire-length parity.

### **A Valued Wire**

Now we have wires, it would be nice to have a valued-wire, where we can see the value of a wire, like an LED on a circuit board. So what we do, is take a wire, say of length $7$, and introduced a named $\star$ square, we'll call it ${\mathcal T}{\star}$, and another named square, we'll call it ${\mathcal F}{\star}$. These are both **unique to each valued wire section, ie. only twice**, and they will only get reused within a single **valued wire**. They are placed in pairs, the two ${\mathcal T}{\star}$ squares right next to each-other, and the two ${\mathcal F}{\star}$ squares next to each-other, with a single $\star$ square separating them. Illustrated below, description from left to right:

* **Left:** A wire.
* **Right:** The square-configuration.

So how do we tell if a wire is true or false? Well, a wire has two states. In each of these states, one of ${\mathcal T}{\star}$ or ${\mathcal F}{\star}$ will be paired in the same tile; the value that is paired is the value of the wire. Illustration below, desciption from left to right:

* **Left, right:** The two states of the **valued wire**;
* **Left:** Wire is valued trued, as the ${\mathcal T}{\star}$ squares share a single tile
* **Right:** Wire is valued false as the ${\mathcal F}{\star}$ squares share a single tile.

We can now have named variable that we can use, to place our ${\rm 3\text{-}S{\small AT}}$ variables down on the grid. We can connect two **valued wires** and force them to have the same value, or if we connect them with an odd-length, force them to have different values; and using wires, we can do this long-distance, across the grid. Using wires, we can propagate the values of the named variables all over the place.

Remaining limitations are:

* We cannot split a wire,
* We cannot cross wires,
* We might have annoying layout issues because we must be careful about wire-length parity.

### **Not-gate**

A **not-gate** is unnecessary as it is implicit: simply using an off-by-one wire length we can negate the value of the wire.

### **A Clause Gate**

Now I can demonstrate a simple clause gadget; it will connect to $3$ wires, and force one of them to be "pulled" state, and force the other two to be in the "pushed" state. We can use this, this is an exactly one-in-three relationship; we set the odd-wire-state to mean "true", and the other two wire-states to mean "false", and we are set.

Illustrations below, descriptions from left to right:

* The wire-layout of the clause gadget. It makes a "plus" sign; the joining of 3 wires in one spot.
* Fill the wire with unique $\star$ squares.
* The three states of the center square. Each of these states "pulls" exactly one wire into the center, the essential point of the gate; to act like a ${\rm 1\text{-in-}3\text{-}S{\small AT}}$ clause.

Now let's take a look at the different states. Illustration below, description from left to right:

* The left wire is pulled into the center; the other two are pushed out.
* The bottom wire is pulled into the center; the other two are pushed out.
* The bottom-right wire is pulled into the center; the other two are pushed out.

Now, if you attach wires with the right length-parity (even or odd length) to the end of this gate, only one of them could be true, the other two false (depending if you attach them oddly, you can generalize this a bit). Thus we can connect $3$ values into a $1\text{-in-}3$ CNF clause.

Remaining limitations are:

* We cannot split a wire,
* We cannot cross wires,
* We might have annoying layout issues because we must be careful about wire-length parity.

### **Splitting a Wire**

To split a wire, we first line up two wires next to each-other. Next, as a visual aid, we label each of the wires with two ${\mathcal T}{\star}$ squares, one next to the other. This will allow us to see when the wire is "true": when the two ${\mathcal T}{\star}$ squares of a wire in a single tile, then it will be true, otherwise false. Each wire should get its *own* pair of ${\mathcal T}{\star}$ pairs, so we'll name one pair ${\mathcal T}\_1{\star}$ and the other ${\mathcal T\_2}{\star}$. Then we introduce three new named-unique $\star$ values, $a{\star},b{\star},c{\star}$. We will place these three next to each-other, once on each wire. However, on one wire, keep a single $\star$ squares between the $a{\star},b{\star},c{\star}$ squares and the ${\mathcal T}{\star}$ pair. On the other wire, put two $\star$ squares between the $a{\star},b{\star},c{\star}$ squares.

Illustration below, description from left to right:

* Wire layout. Note the walls are a bit thick, so the wires are drawn closer together for illustration purposes; in reality, they are a bit farther apart.
* The square-values; the ${\mathcal T}{\star}$ values on top, and the split-connectors $a{\star},b{\star},c{\star}$ beneath.

What this does is force the wires not to be different; if $a{\star},b{\star}$ is tiled on one wire, then the second wire cannot be off-by-one, because then that would imply $a{\star},b{\star}$ is tiled on the second wire, and thus $a{\star},b{\star}$ would be tiled twice. Illustration below, description from left to right:

* Example state of the left wire, valued as true.
* Bad state of the second wire; it tries to be differently valued, but then it gets a duplicate pair.
* Good state of the second wire, now they are the same value, and there are no duplicate pairs.

If you play around with the other two possible states, you will see this extends to those as well, and it works both ways. Thus these two wires are now the same; we have successfully split a wire. We can split the wire as many times as we like, each time using a new set of $a{\star},b{\star},c{\star}$.

Remaining limitations are:

* ~~We cannot split a wire,~~
* We cannot cross wires,
* We might have annoying layout issues because we must be careful about wire-length parity.

### **A Cordless Wire!**

Well, to my delight, splitting a wire turned out to be cordless! That is, in the illustrations above, I lay the wires next to each-other, but there is no reason to! We can place the wires anywhere on the grid, and they'd still be "entangled" so-to-speak. This saves us a lot of trouble:

* We don't even have to worry about crossing wires. This lets us reduce from non-planar variants of ${\rm\mathbf{3\text{-} S{\small AT}}}$
* We have to do any annoying layout, getting the wires to their locations, it is easy! Like a cordless phone! Freedom!
* We don't have to worry about wire-length parity/off-by-one layout.
* We can make pretty minimally sized reduction; the variables will each get a single set of long wire strips, with a lot of cordless connections along the wires. These connections will be to clause-gates, which will reside in its own location on the grid. The clause will now only consist of the clause gadget and three cordless wires sticking out of it.

Remaining limitations are:

* ~~We cannot cross wires,~~
* ~~We might have annoying layout issues because we must be careful about wire-length parity.~~

### **The Reduction, first attempt**

Let $\Phi(\mathbf x)= \bigwedge\_i C\_i$ be a $1\text{-in-}3\text{-}{\rm S{\small AT}}$ boolean formula.

* For each $x\_j \in \mathbf x$, lay-out a single long wire, in rows, near the bottom of the grid.
* For each $C\_i \in \Phi(\mathbf x)$, make a clause-gate at the top of the grid; you can lay them out however you like; best fill it up in a square area, but you can lay it out in a single long row as well.
* For each $x\_j$ variable participating in a clause $C\_i$, place a cordless-wire at one of the $3$ wire-pins of the clause gate; place the other $a{\star},b{\star},c{\star}$ of each connection onto the corresponding variable wire/row. Negated terms should just place the cordless connection to the clause a distance of one farther away, changing the wire-length-parity, and negating the value.

What it might look like:

* **Figure:** A clause, directly connected to cordless wires. "Hotspots" are the way we symbolize the $a{\star},b{\star},c{\star}$ from here on. These hotpots will each be connected to the variables in the grid.

And here is what the grid might look like:

* **Figure:** The resulting game-board. The variables are lined up in rows on the bottom. The clauses are spread out across the top. This layout gives quadratic blowup; a smarter layout can avoid quadratic blowup.

### **Last Minute Details**

Recall the decision problem:

> Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables. But our reduction requires a *lot* of unique variables, much more than $\mathcal O(n)$. There are several ways to solve this issue.

* One way, is to square the size of the grid in both axes. So now our $\mathcal O\left(|\mathbf x|\times \left|\Phi(\mathbf x)\right|\right)$ grid is merely $\in \mathcal O\left(n\right)$, which means all of our unique numbers can be bounded by $n$. Then, we must fill up the rest of the grid, reusing our unique numbers, but being very careful not to place any numbers that our adjacent to each-other in *our* grid, adjacent to each-other in the filler-space of the rest of the grid. There are several creative ways to do this, I'll leave that as an exercise. This method induces an additional quadratic blowup, obviously.
* Another, more succinct, more complex way, is to diversify the $\mathbf 1$ block. Instead of just one building block, we can use $\mathcal O(n)$ building blocks, and then we can reuse the numbers they pair with. This method allows us to avoid quadtratic blowup.

---

### Graph sources
> 22 votes

---
Tags: complexity-theory, np-hard, board-games, tiling
---


# Question
Title: About the complexity of deciding whether no two elements of a collection are the same
Given a collection of $n$ numbers, $S$, the question is to decide whether all the elements of $S$ are distinct from each other. If they are distinct from each other (no two of them are the same), print "Yes". Otherwise print "No".

I know the worst case time complexity of this question is $\Theta \left ( n\log n \right )$. Of course it is based on comparison among elements. But I can't figure out how to prove this. Perhaps using the decision tree?

# Answer
The lower bound $\Omega(n\log n)$ is a classical result of Ben-Or, Lower bounds for algebraic computation trees. The problem itself is known as *element distinctness*, and other lower bounds are proved by reduction to this fundamental lower bound. Ben-Or's lower bound is proved in the *algebraic decision tree* model, a generalization of the comparison model in which each decision can be made on the basis of evaluating the sign of an arbitrary polynomial in the inputs (rather than just the polynomials $a\_i - a\_j$). In order to get a meaningful lower bound, we only allow polynomials of constant degree (the lower bound works for any fixed constant): otherwise we can detect whether all elements are unique by evaluating the polynomial $$ \prod\_{i\<j} (a\_i - a\_j). $$ (The actual model considered by Ben-Or, *algebraic computation trees*, is even more general: he considers "programs" with statements of the form $x = y \pm z$, $x = yz$, $x = y/z$, $x = \sqrt{y}$ and $x = \alpha y$ for real $\alpha$, as well as conditional statements which depend on conditions of the form $x = 0$, $x \> 0$ or $x \geq 0$. Each operation and conditional statement takes unit time, and the lower bound is on the worst-case running time.)

Here is a sketch of the proof in the case where decisions are made based on the sign of *linear* polynomials, following Jeff Erickson's notes. For each node $v$ in the algebraic decision tree, let $R(v)$ be the set of $(a\_1,\ldots,a\_n)$ reaching that node. It is not hard to check that $R(v)$ is connected. For each permutation $\pi \in S\_n$, the set $R\_\pi$ of tuples $(a\_1,\ldots,a\_n)$ ordered according to $\pi$ is connected, but any two $R\_\alpha,R\_\beta$ for $\alpha \neq \beta$ are separated by some region in which the elements are not distinct. The lower bound $\Omega(n\log n)$ immediately follows.

If the allowable conditions have higher degree, then it is no longer true that $R(v)$ is connected; but a deep theorem of Thom and Milner shows that if the decision tree is shallow then each $R(v)$ is composed of "not too many" connected components, and we get the same lower bound. (The same proof idea works for the algebraic computation trees considered by Ben-Or.)

The latest word on the subject (as of 1998) is work of Grigoriev, Karpinski, Meyer auf der Heide and Smolensky, extending the lower bound to randomized algebraic decision trees, and work of Grigoriev extending it to randomized algebraic computation trees. Their proof avoids the use of the deep result of Thom and Milnor mentioned above, and so gives an alternative "elementary" proof of Ben-Or's result.
> 4 votes

# Answer
I think there is something wrong with your claim that the complexity is $\Theta(n \lg n)$. At least, it is not quite that simple. You don't say where you got that claim from, but I don't think it is accurate, at least in general.

The problem can be solved faster, in some machine models. For instance, there are sorting algorithms with running time faster than $\Theta(n \lg n)$, in some machine models, and there are other ways to solve this problem -- e.g., using a hash table using a 2-universal hash function should yield a solution whose expected running time is $\Theta(n)$, under a reasonable model of computation.

What is your machine model? A RAM machine? What notion of complexity are you OK with? Worst-case running time of a deterministic algorithm? Are you OK with a randomized algorithm? The complexity of the problem will depend upon these fine details.
> 4 votes

# Answer
I assume that the collection is stored in an array, if it is not, then it should be able to be moved to one in linear time, unless you have an unusual storage data structure.

One way that it could be done is to first sort $S$, assuming you're sensible and use a good algorithm (whichever you prefer), this will take $\Theta(n \log n)$ time. Now as everything is in order, we know that if there are any duplicates, all the entries with the same value must be next to each other. So we can just do a linear search along the collection, checking each entry against the one after it.
> 0 votes

---
Tags: algorithm-analysis, time-complexity
---


# Question
Title: Are there problems with complexity between $O(n^c/\log^b n)$ and $O(n^{c - \varepsilon})$?
I am having an extremely tough time with this homework question, wondering if anyone could help me (for all you theory aficionados, this one's for you).

*There is a language $L$ with the following property: There is a Turing machine that decides $L$ in time $O(n^{2013}/\log^{2012} n)$, but there is no Turing machine that decides $L$ in time $O(n^{2012.9})$.* Is this statement TRUE or FALSE?

My notion/idea is to use this Corollary that stems from the Time Hierarchy Theorem: *For any two real numbers $1 \le e\_1 \< e\_2$, we have $\mathrm{TIME}(n^{e\_1}) \subsetneq \mathrm{TIME}(n^{e\_2})$*. I think I am on the right track but I need some help with this proof.

# Answer
The question is about upper bound (which is $O(n^{2013} / (\log n)^{2012})$) and lower bound (which is $O(n^{2012.9})$) – do they correspond to each other?

According to definitions of Big-O and Ω we have to find constants $c\_1$, $c\_2$, and $n\_0$ such that for $n\geq n\_0$ two following inequalities are true:

$$c\_1 n^{2012.9} \leq T(n) \leq c\_2 n^{2013} / (\log n)^{2012}.$$

If such constants exist, then the lower bound must be less than upper bound for sufficiently large $n$:

$$c\_1 n^{2012.9} \leq c\_2 n^{2013} / (\log n)^{2012}.$$

Let's simplify this a little:

$$c\_1 (\log n)^{2012} \leq c\_2 n^{0.1}.$$

Can we find $n\_0$ such that this inequality is true when $n \geq n\_0$? Yes, sure – the power function eventually wins over the logarithm function, so the answer is TRUE.
> 4 votes

# Answer
Hint: Find $e\_1,e\_2$ such that $\mathrm{TIME}(n^{2012.9}) \subseteq \mathrm{TIME}(n^{e\_1})$ and $\mathrm{TIME}(n^{e\_2}) \subseteq \mathrm{TIME}(n^{2013}/\log^{2012} n)$. (You also have to take care of the big O's.)
> 4 votes

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


# Question
Title: Construct a context-free grammar for a given set of words
I have seen a few years back a nice and simple algorithm that, given a (finite) set of words in some alphabet, builds a context-free grammar for a language including these words and in some sense "natural" (e.g., the grammar doesn't produce all words in the alphabet). The algorithm is very simple, it has something like 3--4 rules for grammar transformation attempted on each new word. Any help in finding it would be appreciated.

# Answer
I think you might be referring to Sequitur.

**Edit** It has been suggested by other commenters that I leave more information for posterity. Fair point.

Sequitur is an algorithm by Craig Neville-Manning and Ian Witten (of *Managing Gigabytes* fame). It's linear time in the size of the input sequences (although so is the memory usage), and satisfies the twin properties of parsimony (no redundant rules are derived) and utility (every rule is useful).

However, it can't (IIRC) discover arbitrary nesting structure. So a prototypical expression grammar, where an expression can contain an expression, is too much for it. But it will discover word boundaries in English text, and repeat regions in DNA. It's also useful for finding dictionaries for data compression (which is one of Witten's major research interests).
> 2 votes

# Answer
There are also many algorithms for DFA inference: given a set of words, infer a "natural" regular language containing all of those words. For instance, Angluin's L\* is a classic algorithm in this space, but there are many others.

Of course, any regular language is also a context-free language, so this could be used for your purposes as well. Some of the algorithms are beautiful as well as useful in practice.

For more on this topic, you could look at https://stackoverflow.com/q/15512918/781723 and the surrounding literature.
> 0 votes

---
Tags: algorithms, formal-languages, reference-request, formal-grammars, machine-learning
---


title: Laws to simplify a boolean formula

text:
# Question
Title: Laws to simplify a boolean formula
$$ (\neg A \wedge \neg C) \vee (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$ can simplify down to $$ (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$ I've computed the truth tables for the two expressions, and they're the same. But I'm supposed to prove it without using truth tables. What law(s) am I supposed to use?

# Answer
> 1 votes
You have $(\neg A \wedge \neg C) \vee \text{some\_big\_expression} $ and you want to show that it's equivalent to $\text{some\_big\_expression} $.

Simplification rules won't necessarily lead you from the first expression to the second expression. There are systematic ways to test whether two expressions are equivalent, by applying De Morgan's laws in a certain way and other simplification rules (such as $\neg (\neg P) \longrightarrow P$) to transform a formula into equivalent formulas until you reach a disjunctive normal form (or other normal forms, if you apply the laws in a different way). But this doesn't directly get you from one expression to the other.

Another way to prove that two formulas are equivalent is to show that the first implies the second and the second implies the first. Here, it's obvious that $\text{some\_big\_expression}$ implies $(\neg A \wedge \neg C) \vee \text{some\_big\_expression}$, so the difficulty is to prove the opposite implication: $(\neg A \wedge \neg C) \vee \text{some\_big\_expression}$ implies $\text{some\_big\_expression}$. Think about what this means: you want to prove that if $P$ or $Q$ holds then $Q$ holds — in other words, if you already know $Q$, then you don't need to prove $P$, it's already implied by $Q$. This is a consequence of two properties of disjunction, idempotency and monotonicity: if $Q \Rightarrow P$ then $(P \vee Q) \Rightarrow (P \vee P) \Rightarrow P$.

So what's left is to prove that $\neg A \wedge \neg C$ implies $(\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C)$. I'll let you finish. Hint: the right-hand side has both $B$ and $\neg B$, what can you say about these?

Second exercise: use De Morgan's laws to grind the first formula into the second one.

---
Tags: boolean-algebra
---


title: Relative complement of a Non CFL to CFL

text:
# Question
Title: Relative complement of a Non CFL to CFL
Let $L$ be a given Context Free Language over the alphabet $\\{a,b\\}$. Now consider $$L\_1=L-\\{xyx\ |\ x,y\in\\{a,b\\}^\*\\}$$ I know that $\\{xyx\ |\ x,y\in\\{a,b\\}^\*\\}$ is not Context Free (by using pumping lemma).

Based on that can we affirmatively say that $L\_1$ will **NEVER** be Context Free (can't use closure property here, as $\\{xyx\ |\ x,y\in\\{a,b\\}^\*\\}$ is neither *CFL* not *Regular*)?

Or shall $L\_1$ ALWAYS be Context Free ?

# Answer
Please note that $\\{ xyx \mid x,y \in \\{a,b\\}^\*\\}$ is in fact equal to $\\{a,b\\}^\*$ if no further restrictions on $x,y$ are imposed (consider $x=\varepsilon $). Then $L\_1 =\varnothing$ (always) which is trivially regular.
> 1 votes

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


# Question
Title: Kolmogorov Complexity: Why would you need more bytes than the string itself?
I was reading Wikipedia's entry on Kolmogorov Complexity (thanks to this question), which states:

> It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string itself.

Why would you ever need anything more than the string itself to describe it?

# Answer
> 13 votes
The exact value of the Kolmogorov complexity depends on the language chosen to represent strings. This language has to be Turing complete, so representing all strings as themselves isn't an option.

By the pigeonhole principle, if there is at least one string of length at most $n$ whose representation is shorter than itself, then there is also at least one string of length at most $n$ whose representation is longer than itself. (The representation is a compression algorithm.)

You can have a description language where each string has a representation that's at most one bit longer than itself: start each representation with a bit that indicates either “print literally” or “interpret”. Not all description languages are that simple though.

A more formal statement is given further down in the Wikipedia article, in the invariance theorem section. There are *optimal* description languages, such that for any given language, there is a constant $C$ such that the description of any string in the optimal language (no matter what its length is) is at most $C$ bits longer than in that other language. Intuitively, write an interpreter for the other language in the optimal language.

# Answer
> 6 votes
The description of a string considered here is an input to some universal Turing machine. You can think of it as a C program. The string `hello world` does not, by itself, form a C program, but the following one does: `int main(int argc, char *argv[]) { printf("hello world"); }`. As you can see, the overhead is constant but not zero.

---
Tags: kolmogorov-complexity
---


# Question
Title: Binary operators with higher precedence than unary operators
Generally (perhaps always) in programming languages, unary operators have the highest precedence. In some langauges, such as Standard ML, one can dynamically change the precedence of binary operators at run time.

But what if we have a language where binary operators had higher precedence than unary ones? Do such languages exist? And how would we interpret certain cases? For example, let's say binary `+` had higher precedence than unary prefix `@`. In some cases this is obvious because it would mean that

```
@x+y

```

would parse as

```
@(x+y)

```

rather than

```
(@x)+y

```

BUT, how would we parse

```
x + @y

```

Would it be a syntax error (as in it cannot be parsed) or should it parse as `x+(@y)`? I don't mean for this to necessarily be an opinion question; I am more interested to know if any real programming languages exist with high-precedence binary operators, and if so, what do they do.

# Answer
> 1 votes
In Perl, the 'not' operator has lower precedence than +. The expression (false + not 1) evaluates just fine.

---
Tags: context-free, parsing
---


# Question
Title: Theoretical minimum number of registers for a modern computer?
I took a course on compilers in my undergraduate studies in which we wrote a compiler that compiles source programs in a toy Java-like language to a toy assembly language (for which we had an interpreter). In the project we made some assumptions about the target machine closely related to "real" native executables, including:

* a run-time stack, tracked by a dedicated stack pointer ("SP") register
* a heap for dynamic object allocation, tracked by a dedicated heap pointer ("HP") register
* a dedicated program counter register ("PC")
* the target machine has 16 registers
* operations on data (as opposed to, e.g., jumps) are register-to-register operations

When we got to the unit on using register allocation as an optimization, it made me wonder: What is the theoretical minimum number of registers for such a machine? You can see by our assumptions that we made use of five registers (SP, HP, PC, plus two for use as storage for binary operations) in our compiler. While optimizations like register allocation certainly can make use of *more* registers, is there a way to get by with fewer while still retaining structures like the stack and heap? I suppose with register addressing (register-to-register operations) we need *at least two* registers, but do we need more than two?

# Answer
If you allow direct memory access by memory address, then you do not need any "registers" because you can use memory locations instead. For example, memory at location 0 can be the program counter, at location 1 we have the stack pointer, etc. But that is cheating.

So to prevent ourselves from cheating, let us assume there is no direct memory access, because we could use fixed memory locations as registers. Then we can get away with two registers, a program counter and a stack pointer, as explained in the Wikipedia article on stack machines. The stack is only accessible through the stack pointer, and the program is only accessible through the program counter.

Another possibility is to use counter machines. A two-counter machine is Turing complete, i.e., it can compute whatever Turing machine can. This again is nicely explained in the Wikipedia article on counter machines.
> 13 votes

# Answer
The PIC architecture which was introduced by General Instruments in the 1970s and is still in use today had the following registers:

```
W register (not addressible)
01    Timer/Counter
02    Program Counter
03    Status
04    File-Select Register
05-07 One register for each I/O port
08-1F General-purpose registers/"memory"

```

A typical instruction will read a register, perform a computation using the value read and W, and then store the result of the computation either to W or to the register that was read. One of the available computations yields "the value read, ignoring W"; another is "take W, ignoring the value read". The bit patterns that would correspond to "read XX, then take W, ignoring the value read, and store the result in W" are used for NOP as well as a variety of special instructions.

To allow address computations, the processor's execution unit will watch for instructions that encode an address of 00, and substitute the contents of the File Select Register for the address.

Although having to feed all values through the W register can be a bottleneck, the PIC architecture has as a larger working set than other architectures using the same length instruction word. On the PIC16C54 (still made today, and very similar to the 1970's PICs) instructions are 12 bits long. On many other 16Cxx or 16Fxx parts, instructions are 14 bits long and can directly access a 128-byte address space. If the working set of a program fits well with the working set of the instruction set, a statement like "total += value", where "total" and "value" are of type `unsigned char`, would compile to:

```
movf  value,w
addwf total,f

```

On something like the ARM, even if one has a register pre-loaded with the base address of one's variables, the code would be more like:

```
ldr    r0,[r7+value]
ldr    r1,[r7+total]
add    r1,r1,r0
str    r1,[r7+total]

```

In many cases, a compiler would be able to avoid doing loads and stores with every operation, but on something like the PIC, the benefits of the larger working set can sometimes outweigh the limitations of having to go through W all the time.
> 1 votes

---
Tags: compilers, computer-architecture
---


# Question
Title: NP-hardness given some reducible language
While reading a passage in an older textbook I came upon this problem which I am having difficulty in justifying whether its true or false. Is this possible?

If some problem $A$ is NP-hard, and if that problem $A$ can be reduced to problem $B$, and there exists some polynomial-time algorithm which solves $B$, then P=NP?

While I understand that the view is $P≠NP$, if the above case were true would $P=NP$?

# Answer
Hint: if $A$ is NP-hard, and it can be reduced in polynomial time to $B$, what can you say about $B$? Then if you have a polynomial time algorithm for $B$, what does that imply? (Check out the definition of NP-hardness and NP-completeness).
> 1 votes

---
Tags: graphs, np-hard
---


# Question
Title: Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?
I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example:

Assume the following regular expression:

```
((a(b+))+(a|c))|a|c

```

Why is it that this accepts the strings:

```
a
c
abba
abbabbba
abbabbc

```

etc

But when I flip it around and use the regular expression

```
a|c|((a(b+))+(a|c))

```

I can now only ever get the following strings when I check it with a RegExp tester:

```
a
c

```

I know it is to do with the order of precedence but I don't understand why, please could somebody enlighten me?

# Answer
> 3 votes
Both the patterns match your given strings and are equivalent. The problem here is that your tester does not try to match the string against the pattern, but tries to find matching substrings, and it does that by trying each of the ORed patterns in order. Hence the second pattern stops when $a$ is matched, but the first one matches the whole string.

To see the difference Look at the below code, written in Java:

```
public static void main(String[] args) {
    test("((a(b+))+(a|c))|a|c", "abbabbc");
    test("a|c|((a(b+))+(a|c))", "abbabbc");
}

private static void test(String pattern, String str) {
    System.out.println(str.matches(pattern));
    Matcher matcher = Pattern.compile(pattern).matcher(str);
    while(matcher.find())
        System.out.println(str.substring(matcher.start(), matcher.end()));
}

```

The output is

```
true
abbabbc
true
a
a
c

```

which shows that both patterns do match $abbabbc$. They are only different in eyes of a *matching-substrings-finder* program.

# Answer
> -4 votes
You can't write 3 ORs.

Example:

A or B or C =\> it will compare A or B and ignore C ((a(b+))+(a|c))|a|c the last "|c" ignored. The proof, does it accept "abcc" ?

likewise a|c|((a(b+))+(a|c)) the "|((a(b+))+(a|c))" ignored and only a|c left.

Good Luck.

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


# Question
Title: Discrete fourier transform of a polynomial whose degree is not a power of 2
I need to evaluate a polynomial of degree n at the n cube roots of unity. Simple evaluation would take $O(n^2)$ time. I know that polynomial evaluation can be done in $O(n\log n)$ time using FFT.

But the problem that I am facing is this. FFT only works when $n$ is a power of 2. If I extend my polynomial by appending zeroes at the end, that would not solve my problem because then I would be evaluating my polynomial at cube roots of $m$ (where $m$ is a power of $2$ greater than $n$) which I don't want.

Any ideas on this?

# Answer
> 3 votes
There are FFT algorithms for prime sizes such as Rader's algorithm. Given a factorization of $n$ as a product of (not necessarily different) primes, you can compute the DFT by running Rader's algorithm for each prime, in the same way that the usual FFT works by in effect computing FFTs of size $2$. You can read the details in a paper by Frigo and Johnson which describes the FFTW library, which computes length $n$ DFTs in $O(n\log n)$ for all $n$. You can also just use the library if all you really need to do is compute FFTs (rather than solve some programming exercise in some course).

---
Tags: algorithms, divide-and-conquer, polynomials
---


# Question
Title: Prove that $TQBF \notin SPACE(n^{\frac{1}{3}})$
I would like some hints on how to approach this problem, I know for instance that $TQBF$ is $PSPACE$-$Complete$, so it can solved in poly space and any other $PSPACE$-$Complete$ problems can be log spaced reduced to $TQBF$. I believe that I need to employ the space hierarchy theorem in some way but I am not sure how, this is a homework question so I just want a hints. Thank you!

# Answer
> 4 votes
The argument is actually surprisingly delicate. This sketch follows Tompa's *Introduction to computational complexity*, Chapter 10. The space hierarchy theorem shows that there is some problem $L \in \mathrm{SPACE}(n^{1+\epsilon}) \setminus \mathrm{SPACE}(n)$ for every $\epsilon \> 0$. Since TQBF is PSPACE-complete, there is some logspace reduction from $L$ to TQBF. But we actually know more - using Savitch's theorem, we can come up with some reduction which blows up instances of $L$ of size $n$ to instances of TQBF of size $O(n^{2(1+\epsilon)} \log n)$ (at least according to Ryan Williams, page 1 at the bottom). If TQBF were solvable in space $O(n^\delta)$ then this would give an algorithm for $L$ in space $O(n^{2\delta(1+\epsilon)})$. Taking the limit $\epsilon \to 0$, this shows that $\delta \geq 1/2$.

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


# Question
Title: Prove the red blue separation problem is NP-complete
Consider the following problem: given a set of $m$ red points and $n$ blue points in the plane, find a minimum length cycle that separates the red points from the blue points. That is, the red points are inside the cycle and the blue points are outside the cycle, or vice versa. This problem is called the *red blue separation problem*.

I am trying to reduce the Traveling Salesman Problem (TSP) to this but I am getting nowhere. Can you please help me with this? Any help is appreciated.

# Answer
A *separating polygon* separating a set of points $S$ from a set of points $T$ is a simple polygonal circuit $P$ for which every point of $S$ is interior or on the boundary of $P$, and every points of $T$ is exterior or on the boundary of $P$. Let $D(P)$ denote the perimeter of a polygon $P$, that is, the sum of the Euclidean lengths of the edges of $P$. If $P$ is a separating polygon for $S$ and $T$ with minimum value of $D(P)$, then $P$ is called a *minimum separating polygon*.

The problem you describe is known as the *minimum separating polygon problem* (MSP), formally:

> *Instance:* Two finite point sets $S$ and $T$, and an integer $k$.
>
> *Question:* Is there a separating polygon $P$ for the sets $S$ and $T$ such that $D(P) \leq k$?

MSP is NP-hard. The hardness was first shown by Eades and Rappaport by a reduction from TSP, see \[1\], Section 2 for the reduction.

---

\[1\] Eades, Peter, and David Rappaport. "The complexity of computing minimum separating polygons." Pattern Recognition Letters 14.9 (1993): 715-718.
> 4 votes

---
Tags: algorithms, algorithm-analysis, np-complete, np-hard, np
---