On my favourite TCS site cstheory.stackexchange.com I found a simple question about the Post Correspondence Problem:
If the upper and lower words of each domino must have different lengths, is the problem still undecidable? (we call this variant $PCP^{\neq}$).
The answer is yes, it remains undecidable …
Continue readingThis is a simple note on Turing completeness of 2-neighbourhood 1-dimensional Cellular Automata.
A Cellular Automaton (pl. Cellular Automata) is a model of computation based on a grid of cells that evolve according to a simple set of rules. The grid can be multi-dimensional, the most famous and studied cellular automata are 1-dimensional and 2-dimensional. Each cell can be in a particular finite state ($k$-states CA), at each step of the evolution (generation) the cell changes its state according to its current state and the state of its neighboring cells. The number of neighbours considered is finite; for a 1-dimensional CA, the usual choice is the adjacent neighbours. A m-neighbourhood 1-dimensional CA is a CA in which the next state of cell $c_i$ depends on the state of $c_i$ and the state of the $m-1$ adjacent cells; usually $c_i$ is the central cell.
Formally, if $t_n(c_i)$ is the state of cell $c_i$ at time $t_n$:
$$t_{n+1}(c_i) = f( t_n(c_{i-\ell}), …, t_n(c_{i-2}), t_n(c_{i-1}), t_n(c_i), t_n(c_{i+1}), t_n(c_{i+2}), …, t_n(c_{i+\ell}) )$$
and $m = 2\ell+1$.
For more details and basic references see: Das D. (2012) A Survey on Cellular Automata and Its Applications.
Even basic cellular automata can be Turing Complete, for example see the (controversial) proof of Turing completeness of the 3-neighbourhood Cellular Autaton identified by Rule 110 .
If only 1 neigbour is considered (i.e. the next state of a cell only depend on its current state), then we cannot achieve Turing completeness. But with 2-neighbourhood and enough states it’s possible to emulate every CA.
Continue reading(“A few lines where incompressibility meets unprovability”)
The Kolmogorov Complexity $K(x)$ of a string $x$ relative to an Universal Turing machine $U$ is the length of the shortest program $p$ that “prints” $x$:
$$K(x) = min\{ |p| \mid U(p) = x \}$$
A string $x$ is incompressible if $K(x) \geq |x|$. Assuming a binary alphabet $\Sigma = \{0,1\}$, for each $n \geq 1$, there are $2^n$ strings of length $n$, but there are only $2^n-1$ programs shorter than $n$, so there is at least one incompressible string among them. And it follows immediately that there are infinite incompressible strings (they exist …).
Can we catch some of them? … No! Indeed if we are reasoning in a formal theory $T$ that is powerful enough to formalize Turing machines and the notion of compressibility – e.g. Peano Arithmetic – we have:
Theorem 1: There exists $n$ such that for all strings $x$ such that $|x| \geq n$ the statement “$K(x) \geq |x|$” (i.e. $x$ is incompressible) is unprovable in $T$.
Proof: Suppose that there are infinitely many strings $x$ such that there is a proof of “$K(x) \geq |x|$”. We can build a program $p$ that enumerates all valid proofs of $T$ and whenever it founds a proof of “$K(x_i) \geq |x_i|$” for some $x_i$, it compares $|x_i|$ with $|p|$ (by the recursion theorem we can build a program that knows its length), and if $|p| < |x_i|$ then $p$ halts and prints $x_i$. So $T$ proves that $x_i$ is incompressible, but we can actually build a program shorter than $|x_i|$ which prints $x_i$, a contradiction.
Note that Theorem 1 is not provable in $T$ ! … we need $T + Con(T)$ to prove it, because no powerful enough theory can prove its own consistency or prove that some sentence is unprovable.
While thinking about simple “puzzles” that seem hard at a first glance, but have not enough rules and structural constraints that make it easy to prove that they are NP-complete, I designed the following game (but perhaps it has already a name … let me know if you know it 🙂 ):
A simple javascript version of the game can be played here.
The rules are simple, but even in a small game with a 4×4 home area it’s hard to find the correct shift sequence …
Continue readingIt is well known that $\text{Primes}= \{ a^p \mid p \text{ is prime}\}$ is not regular. The standard proof uses the pumping lemma for regular languages, but you can also use Parikh’s theorem or Myhill-Nerode theorem: see this question on cs.stackexchange.com. I tried to figure out another way to prove it, and came out with an alternate proof that uses a bit of number theory and Busy Beavers.
First of all: Theorem 1 (Prime gap theorem). There are gaps between primes that are arbitrarily large.
Continue readingI just bought the nice book “Problems with a POINT – Exploring Math and Computer Science” by William Gasarch and Clyde Kruskal. The book explains many nice mathematical and theoretical computer science problems that are “easy-to-understand-but-not-so-easy-to-solve”, and most of them solicit the reader’s curiosity and invite him to futher explore the related topics (plenty of references are given at the end of each chapter).
Chapter 23 explains a sane reduction between COL4 (the problem of deciding whether a graph is 4-colorable) to COL3 (the problem of deciding whether a graph is 3-colorable). Both are well known NP-complete problems. I started reading the chapter, but suddenly stopped and tried to figure out a reduction by myself.
The idea presented in the book is to replace each node of the graph $G$ of the COL4 problem with four nodes, force them to be colorable with colors F and T (the third color R is not allowed), force exactly one of them to be T, and finally adding a gadget that prevents two adjacent quadruples from having two corresponding nodes colored with T.
I came up with a very similar reduction, but the gadgets involved are slightly smaller: indeed a 4 colorable node can be represented “in binary” with two nodes each one colorable with T or F (two bits).
Continue readingWhat happens if a modern constraint satisfaction and optimization program decides to play a Video Game Classic?
A one-state Turing machine is a very weak device: it has no internal memory and it cannot even recognize the trivial language $L = \{1\}$. Its transition function is a simple map $\delta : \Sigma \to \Sigma \times \{L,R\}$, i.e. given the symbol under its head it can rewrite it with another one and move left or right, but the state remains the same. Nevertheless it can use its ability to write on the tape to “gain” some memory; in particular in each cell $C_i$ of the tape it can store:
This information is enough to build $k$-ary counters and also a sort of comparator between numbers written in different bases. So, some one-state Turing machines can “recognize” languages that are not Context-Free (the quotes are due to a different accept/reject conditions that are necessary because we cannot distinguish between accepting and non accepting states).
After a long time, here we are again … let’s resume with a small (and rather trivial) post …
Busy Beavers are allmost incompressible! … easy fact, but I didn’t find it anywhere.
Recently A. Amarilli (a3nm) posted a question on cs.stackexchange.com about the computational complexity of a Test Round problem of the Google France #Hash Code 2015: the “Pizza Regina” problem (March 27th, 2015):
Definition [Pizza Regina problem]
Input: A grid $M$ with some marked squares, a threshold $T\in \mathbb{N}$, a maximal area $A \in\mathbb{N}$
Output: The largest possible total area of a set of disjoint rectangles with integer coordinates in $M$ such that each rectangle includes at least $T$ marked squares and each rectangle has area at most $A$.
The problem can be converted to a decision problem adding a parameter $k \in \mathbb{N}$ and asking:
Question: Does there exist a set of disjoint rectangles satisfying the conditions (each rectangle has integer coordinates in $M$, includes at least $T$ marked squares and has area at most $A$) whose total area is at least $k$ squares?
The problem is clearly in $\mathsf{NP}$, and after struggling a little bit I found that it is $\mathsf{NP}$-hard (so the Pizza Regina problem is $\mathsf{NP}$-complete). This is a sketch of a reduction from MONOTONE CUBIC PLANAR 1-3 SAT:
Continue reading
We assume that reader is familiar with the notions of undecidability, Turing reductions, Kolmogorov complexity, Halting problem, and related subjects.
The (easy) proof that the uncomputability of Kolmogorov complexity implies the undecidability of the Halting problem can be found in many lectures notes and books; usually the proof assumes that the Halting problem is decidable and derive the computability of Kolmogorov complexity which is a contradiction. In other words given an oracle for the Halting problem, we can compute the Kolmogorov complexity of a string $x$.
But we can also derive the uncomputability of Kolmogorov complexity from the undecidability of the Halting problem; the proof is “less popular” but nevertheless can be found after a few searches on Google. For example the technical report: Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995) contains two different proofs, and the great book Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications presents it as an exercise (with a hint on how to solve it that is credited to P. Gács by W. Gasarch in a personal communication Feb 13, 1992). Here we give an extended proof, with more details, that the Halting problem can be decided using an oracle that computes the Kolmogorov complexity of a string, i.e. that the Halting problem is Turing reducible to the Kolmogorov complexity. Continue reading
Abstract: Subway shuffle is an addicting puzzle game created by Bob Hearn. It is played on a graph with colored edges that represent subway lines; colored tokens that represent subway cars are placed on the nodes of the graph. A token can be moved from its current node to an empty one, but only if the two nodes are connected with an edge of the same color of the token. The aim of the game is to move a special token to its final target position. We prove that deciding if the game has a solution is PSPACE-complete even when the game graph is planar.
While thinking about possible answers to the question “Listing of strongly NP-complete problems” I came up with this simple numeric strongly NP-complete problem:
[SQUARE-FREE SUBSET PRODUCT] Given $3N$ integers, find $N$ of them whose product is square free.
I didn’t find it anywhere, so it can be somewhat “original”.
NPC Pills (NP-Complete pills) is a collection of some NP-completeness proofs that I posted on the Q&A sites cstheory.stackexchange.com and cs.stackexchange.com. Up to my knowledge they are original and some of them are not so trivial. At present, most of them are just sketches that contain the NP-hardness reduction idea, but for some of them I wrote (or I’m going to write) a more formal paper. If you are particularly interested in one of them write me an email.
The following variant of the 3-Dimensional Matching problem (3DM) was posted on cstheory.stackexchange.com, a question and answer site for professional researchers in theoretical computer science and related fields:
Definition. 3-DIMENSIONAL MATCHING VARIANT
Input: Set $M \subseteq X \times Y \times Z$ where $X,Y,Z$ are disjoint sets; we call $M_{XY}= \{(x,y)\mid \exists z \text{ s.t. } (x,y,z)\in M \}$ the set of pairs of $X \times Y$ that appear in the triples of $M$, and $M_{XZ}= \{(x,z)\mid \exists y \text{ s.t. } (x,y,z)\in M \}$ the set of pairs of $X \times Z$ that appear in the triples of M.
Question: Does there exist a set $M’ \subseteq M \cup M_{XY} \cup M_{XZ} $ such that every element of $X \cup Y \cup Z$ is included in a triple or a pair of $M’$ exactly once?
Informally we want to build an exact cover of $X \cup Y \cup Z$ using the triples of $M$ or one of the two pairs $(x,y), (x,z)$ that are contained in a triple $(x,y,z) \in M$.
The problem is NP-complete, click the following link to download the technical report with the reduction (we also discuss some other variants of the problem).
Click here to download the technical report
If you have some comments or find some errors, contact me via email.
This is the first of a new series of posts that I tagged with “Yet Another (Tiny) Open Problem”. In these posts I’ll describe some well known or original problems in Theoretical Computer Science that are still unsolved (up to my knowledge). Many of them are not so relevant, so I also added a “Tiny” in the acronym. If you discover that they have been solved or partially solved or, even better, YOU SOLVED them, let me know; I’ll try to keep their open/close status up-to-date.
We begin with a weird problem that involves those cute animals known as Busy Beavers : in computational theory a busy beaver is a Turing machine that attains the maximum number of steps performed before halting or the number of nonblank symbols finally on the tape, among all Turing machines of the same size. The Turing machine must follow some rigid design specifications: it operates on a single two-way unbounded tape initially filled with $0$s and the tape alphabet is $\{0,1\}$ (0 is the blank symbol); it has $n$ states plus a halting state, and every transition is a 5-tuple: (current non-halting state, current symbol, symbol to write, direction of shift, next state). Continue reading