What happens if a modern constraint satisfaction and optimization program decides to play a Video Game Classic?

Continue reading# The Power of One-State Turing Machines

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:

- the number $n$ of times the head visited $C_i$ modulo a fixed constant $k$;
- if it has entered $C_i$ from the left or from the right.

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).

# Busy Beavers are (allmost) incompressible

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.

# NPC Pill #5: (P)izza =?= (NP)izza

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

# Using Kolmogorov complexity to solve the Halting problem

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

# Subway Shuffle is PSPACE-complete

**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.

# NPC Pill #4: Square-Free Subset Product

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 Pill #3: Pick 3 or Pick 2 … another NP-complete 3DM variant

*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.

# NPC Pill #3: Pick 3 or Pick 2 … another NP-complete 3DM variant

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.

# YATOP #1: Are busy beavers lonely creatures?

This is the first of a new series of posts that I tagged with “**Y**et **A**nother (**T**iny) **O**pen **P**roblem”. 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

# NPC Pill #2: Minimal TSP Tour is coNP-Complete

*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.

# NPC Pill #2: Minimal TSP Tour is coNP-Complete

The *Traveling Salesman Problem* (TSP) is a well–known problem from graph theory: we are given $n$ cities and a nonnegative integer distance $d_{ij}$ between any two cities $i$ and $j$ (assume that the distances are symmetric, i.e. for all $i,j, d_{ij} = d_{ji}$). We are asked to find the* shortest tour* of the cities, that is a permutation $\pi$ of $[1..n]$ such that

$\sum_{i=1}^n d_{\pi(i),\pi(i+1)}$ (where $\pi(n+1) = \pi(n)$) is as small as possible. Its well-known NP-complete version is the following (TSPDECISION): If a nonnegative integer bound $B$ (the traveling salesman’s “budget”) is given along with the distances, does there exist a tour of all the cities having total length no more than $B$?

But what about checking that a tour has effectively minimal length? We prove that the problem:

TSPMINDECISION: Given a set of $n$ cities, the distance between all city pairs and a tour $T$, is T visiting each city exactly once and is T of minimal length?

is coNP-complete. As a secondary result we prove that given a graph $G$ and an Hamiltonian path, it is NP-complete to check if $G$ contains an Hamiltonian cycle as well.

**UPADTE 2014-03-21**: after publishing the proof on arXiv, it turned out that the same result was proved Papadimitriou and Steiglitz in [1] (see also [2] Section 19.9). Our proof is slightly different and it may be interesting in and of itself, so we decided not to withdraw the paper.

[1] Christos H. Papadimitriou and Kenneth Steiglitz. 1982. *Combinatorial Optimization: Algorithms and Complexity*. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.

[2] Christos H. Papadimitriou and Kenneth Steiglitz. *On the Complexity of Local Search for the Traveling Salesman Problem*. SIAM J. Comput., 6(1), 76–83, 1977.

# NPC Pill #1: Single Overlap RX3C

*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.

# NPC Pill #1: SINGLE OVERLAP RX3C

The EXACT COVER BY 3-SETS (X3C) problem is:

**Instance**: Set $X = \{x_1,x_2,…,x_{3q}\}$ and a collection $C = \{C_1,…,C_m\}$ of 3-element subsets of $X$.

**Question**: Does $C$ contain an exact cover for $X$, i.e. a subcollection $C’ \subseteq C$ such that every element of $X$ occurs in exactly one member of $C’$?

X3C is NP-complete [1], and as shown in [2] it remains NP-complete even if every element $x_i$ contained in exactly 3 subsets of $C$ (*Restricted Exact Cover by 3-Sets* – RX3C).

We proved that it remains NP-complete even if every pair of subsets in $C$ share at most one element; i.e. for all $i \neq j,\; | C_i \cap C_j | \leq 1$ and we call this restricted version * SINGLE OVERLAP RX3C*.

- Link to the original question on cstheory
- Printed page with the question and a sketch of the proof (NPC_Pill_001_restriction_of_exact_cover_by_3_sets.pdf)

[1] M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7.

[2] Teofilo F. Gonzalez: Clustering to Minimize the Maximum Intercluster Distance. Theor. Comput. Sci. 38: 293-306 (1985).

# Weapon-target assignment problem

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

# New domain nearly42.org

We moved from fractalmuse.org to nearly42.org …

# The Crazy Frog Puzzle and Permutation Reconstruction from Differences

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

# Complexity of the Hidden Polygon Puzzle

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.