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.
It 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 readingA 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.
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.
The decision version of the Weapon-Target Assignment (WTA) problem is as follows:
There are a number of weapons and a number of targets. The weapons are of type $i = 1, \ldots, m$ . There are $W_{i}$ available weapons of type $i$. Similarly, there are $j = 1, \ldots, n$ targets, each with a value of $V_{j}$ . Any of the weapons can be assigned to any target. Each weapon type has a certain probability of destroying each target, given by $p_{i,j}$ . Does there exist a weapon-target assignment such that:
$$D = \sum_{j=1}^n V_j \prod_{i=1}^m q_{i,j}^{x_{i,j}} \leq k$$
where $k$ is a given integer; $x_{i,j} = 1$ if weapon $i$ is assigned to target $j$, $x_{i,j} =0$ otherwise; $q_{i,j} = 1 – p_{i,j}$ is the survival probability of target $j$ when hit by weapon $i$. No more than $W_i$ weapons of type $i$ can be used, so we must add the following constraint:
$$\sum_{j=1}^n x_{i,j} \leq W_i \quad \mbox{ for } i = 1,\ldots,m$$
WTA problem is NP complete (see L. Chen, C. J. Ren, and S. Deng, “An efficient approximation for weapon-target assignment,” vol. 1, Computing, Communication, Control, and Management. ISES International Colloquium, 2008, pp. 764-767), we give an alternate hardness proof using a reduction from the NP-complete SUBSET PRODUCT problem. Continue reading
The Crazy Frog Puzzle (CFP) is the following: we have a $n \times n$ partially filled board, a crazy frog placed on an empty cell and a sequence of horizontal, vertical, and diagonal jumps; each jump has a fixed length and two possible opposite directions. The crazy frog must follow the sequence of jumps, and at each step it can only choose among the two available directions. Can the frog visit every empty cell of the board exactly once (it cannot jump on a blocked cell and on the same cell two times)?
Figure 1: an example of the Crazy Frog Puzzle on the left and its solution on the right.
We prove that the Crazy Frog Puzzle is $\sf{NP}$-complete even if restricted to 1 dimension and even without blocked cells. The 1-D CFP without blocked cells corresponds to the problem of reconstructing a permutation from its differences:
Permutation Reconstruction from Differences problem:
Input: a set of $n-1$ distances $a_1,a_2,…,a_{n-1}$
Question: does exist a permutation $\pi_1,…,\pi_n$ of the integers $[1..n]$ such that $| \pi_{i+1} – \pi_i| = a_i$, $i=1,…,n-1$ ?
For example, given the differences $(2,1,2,1,5,3,1,1)$ a valid permutation of $[1..9]$ is $(5,7,6,8,9,4,1,2,3)$
Update 2013-12-19: a new version of the paper is available.
click here to download a draft of the paper
The Hidden Polygon Puzzle (for brevity HPP) decision problem is:
Input: a set $P$ of $m$ integer points on a $n \times n$ square grid and an integer $k \leq m$;
Question: does exist a simple rectilinear polygon with $k$ or more vertices $(v_1,v_2, …, v_t), \; v_i \in P, t \geq k$?
The following figure shows an example of a HPP puzzle.
Figure 1: Given the 21 points on the right, can we find
a simple rectilinear polygon with at least 16 vertices?
A possible solution is shown on the right.
The problem is a slight variant of the $\sf{NP}$-complete puzzle game Hiroimono; we prove that the Hidden Polygon Puzzle is $\sf{NP}$-complete, too using a completely different reduction.
Hidato (also known as Hidoku) is a logic puzzle game invented by Dr. Gyora Benedek, an Israeli mathematician. The rules are simple: given a grid with $n$ cells some of which are already filled with a number between $1$ and $n$ (the first and the last number are circled), the player must completely fill the board with consecutive numbers that connect horizontally, vertically, or diagonally.
Figure 1: An Hidato game (that fits on a $8 \times 8$ grid) and its solution on the right.
We prove that the corresponding decision problem $\sf{HIDATO}$ : “Given a Hidato game that fits in a $m \times n$ grid, does a valid solution exist?” is $\sf{NP}$-complete.
Binary Puzzle (also known as Binary Sudoku) is an addictive puzzle played on a $n \times n$ grid; intially some of the cells contain a zero or a one; the aim of the game is to fill the empty cells according to the following rules:
We prove that the decision version of Binary Puzzle is NP-complete.
The node deletion game NODE KAYLES is a two persons perfect information game played on a graph $G$. Players alternate picking a node from the graph $G$; the node and its adjacent nodes are deleted. The first player unable to move loses the game. Deciding the winner of a NODE KAYLES game is $\mathsf{PSPACE}$-complete [1]. Similarly in the EDGE KAYLES [1] game the two players must pick an edge; the edge is deleted along with the two endpoint nodes and the edges incident to its two endpoint nodes. The complexity of finding the winner of a EDGE KAYLES game is unknwon. On the Q&A site cstheory.stackexchange.com I submitted a mix of the two games; I call it the BRIDGES AND ISLANDS game: at each turn each player must pick an edge (a “bridge”) or an isolated node (an “island”); if a player picks a node the node is deleted along with its incident edges, if it picks an edge, the edge is deleted along with its two endpoint nodes and the edges incident to them. Like the other two games, the first player unable to move loses the game. I didn’t succeed in finding the complexity of BRIDGES AND ISLANDS.
However decideng the winner is polynomial time solvable when the three games are played on a path. Here I give a quick proof for EDGE KAYLES; the proof for the other two games is similar. Continue reading
On Jan 17 I asked the following question on cs.stackexchange.com:
What is the complexity of the following variant of the SUBSET-SUM decision problem?
2-BIT SUBSET SUM: Given an integer $m \geq 0$, and a set of nonnegative integers $A = \{x_1, x_2, …, x_n\}$ such that every $x_i$ has at most $k=2$ bits set to $1$ ($x_i = 2^{b_{i_1}}+2^{b_{i_2}},\;\; b_{i_1},b_{i_2}\geq 0$); is there a subset $A’ \subseteq A$ such that the sum of its elements is equal to $m$ ?