We study the computational complexity of the following two-player game. The instance is a graph G = (V,E), an initial vertex s ∈ V, and a target set T ⊆ V. A “cat” is initially placed on s. Player 1 chooses a vertex in the graph and removes it and its incident edges from the graph. Player 2 moves the cat from the current vertex to one of the adjacent vertices. Players 1 and 2 alternate removing a vertex and moving the cat, respectively. The game continues until either the cat reaches a vertex of T or the cat cannot be moved. Player 1 wins if and only if the cat cannot be moved before it reaches a vertex of T. It is shown that deciding whether player 1 has a forced win on the game on G is PSPACE-complete.

We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t2(n) is a time-constructible function and t2(n) grows faster than t1(n+1), then there exists a language which can be accepted by a t2(n)-time nondeterministic cellular automaton but not by any t1(n)-time nondeterministic cellular automaton.

A disentanglement puzzle consists of mechanically interlinked pieces, and the puzzle is solved by disentangling one piece from another set of pieces. A cast puzzle is a type of disentanglement puzzle, where each piece is a zinc die-casting alloy. In this paper, we consider the generalized cast puzzle problem whose input is the layout of a finite number of pieces (polyhedrons) in the 3-dimensional Euclidean space. For every integer k ≥ 0, we present a polynomial-time transformation from an arbitrary k-exponential-space Turing machine M and its input x to a cast puzzle c1 of size k-exponential in |x| such that M accepts x if and only if c1 is solvable. Here, the layout of c1 is encoded as a string of length polynomial (even if c1 has size k-exponential). Therefore, the cast puzzle problem of size k-exponential is k-EXPSPACE-hard for every integer k ≥ 0. We also present a polynomial-time transformation from an arbitrary instance f of the SAT problem to a cast puzzle c2 such that f is satisfiable if and only if c2 is solvable.

Kurotto and Juosan are Nikoli's pencil puzzles. We study the computational complexity of Kurotto and Juosan puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.

The Building puzzle is played on an N×N grid of cells. Initially, some numbers are given around the border of the grid. The object of the puzzle is to fill out blank cells such that every row and column contains the numbers 1 through N. The number written in each cell represents the height of the building. The numbers around the border indicate the number of buildings which a person can see from that direction. A shorter building behind a taller one cannot be seen by him. It is shown that deciding whether the Building puzzle has a solution is NP-complete.

Shisen-Sho is a tile-based one-player game. The instance is a set of 136 tiles embedded on 817 rectangular grids. Two tiles can be removed if they are labeled by the same number and if they are adjacent or can be connected with at most three orthogonal line segments. Here, line segments must not cross tiles. The aim of the game is to remove all of the 136 tiles. In this paper, we consider the generalized version of Shisen-Sho, which uses an arbitrary number of tiles embedded on rectangular grids. It is shown that deciding whether the player can remove all of the tiles is NP-complete.

This paper investigates relationships among deterministic, nondeterministic, and alternating complexity classes defined in the hyperbolic space. We show that (i) every t(n)-time nondeterministic cellular automaton in the hyperbolic space (hyperbolic CA) can be simulated by an O(t4(n))-space deterministic hyperbolic CA, and (ii) every t(n)-space nondeterministic hyperbolic CA can be simulated by an O(t2(n))-time deterministic hyperbolic CA. We also show that nr+-time (non)deterministic hyperbolic CAs are strictly more powerful than nr-time (non)deterministic hyperbolic CAs for any rational constants r 1 and > 0. From the above simulation results and a known separation result, we obtain the following relationships of hyperbolic complexity classes: Ph= NPh = PSPACEh EXPTIMEh= NEXPTIMEh = EXPSPACEh , where Ch is the hyperbolic counterpart of a Euclidean complexity class C. Furthermore, we show that (i) NPh APh unless PSPACE = NEXPTIME, and (ii) APh EXPTIME h.

Golf is a solitaire game, where the object is to move all cards from a 5×8 rectangular layout of cards to the foundation. A top card in each column may be moved to the foundation if it is either one rank higher or lower than the top card of the foundation. If no cards may be moved, then the top card of the stock may be moved to the foundation. We prove that the generalized version of Golf Solitaire is NP-complete.

A Manhattan tower is a monotone orthogonal polyhedron lying in the halfspace z ≥ 0 such that (i) its intersection with the xy-plane is a simply connected orthogonal polygon, and (ii) the horizontal cross section at higher levels is nested in that for lower levels. Here, a monotone polyhedron meets each vertical line in a single segment or not at all. We study the computational complexity of finding the minimum number of guards which can observe the side and upper surfaces of a Manhattan tower. It is shown that the vertex-guarding, edge-guarding, and face-guarding problems for Manhattan towers are NP-hard.

Forty Thieves is a solitaire game with two 52-card decks. The object is to move all cards from ten tableau piles of four cards to eight foundations. Each foundation is built up by suit from ace to king of the same suit, and each tableau pile is built down by suit. You may move the top card from any tableau pile to a tableau or foundation pile, and from the stock to a foundation pile. We prove that the generalized version of Forty Thieves is NP-complete.

The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. The chromatic art gallery problem is to find a guard set for P such that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons with r-visibility when the number of colors is k=2. Here, two points are r-visible if the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is an r-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is k=2.

A number-conserving cellular automaton (NCCA) is a cellular automaton (CA) such that all states of cells are represented by integers and the sum of the cell states is conserved throughout its computing process. It can be thought of as a kind of modelization of the physical conservation law of mass or energy. It is known that the local function of a two-dimensional 45-degree reflection-symmetric von Neumann neighbor NCCA can be represented by linear combinations of a binary function. In spite of the number-conserving constraints, it is possible to design an NCCA with complex rules by employing this representation. In this paper, we study the case in which the binary function depends only on the difference of two cell states, i.e., the case in which the function can be regarded as a unary one and its circuit for applying rules to a cell only need adders and a single value table look up module. Even under this constraint, it is possible to construct a logically universal NCCA.

Moon-or-Sun, Nagareru, and Nurimeizu are Nikoli's pencil puzzles. We study the computational complexity of Moon-or-Sun, Nagareru, and Nurimeizu puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.

Usowan is one of Nikoli's pencil puzzles. We study the computational complexity of Usowan puzzles. It is shown that deciding whether a given instance of the Usowan puzzle has a solution is NP-complete.

Herugolf and Makaro are Nikoli's pencil puzzles. We study the computational complexity of Herugolf and Makaro puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.

We study the problem of determining the minimum number of open-edge guards which guard the interior of a given orthogonal polygon with holes. Here, an open-edge guard is a guard which is allowed to be placed along open edges of a polygon, that is, the endpoints of the edge are not taken into account for visibility purpose. It is shown that finding the minimum number of open-edge guards for a given orthogonal polygon with holes is NP-hard.

Calculation is a solitaire card game with a standard 52-card deck. Initially, cards A, 2, 3, and 4 of any suit are laid out as four foundations. The remaining 48 cards are piled up as the stock, and there are four empty tableau piles. The purpose of the game is to move all cards of the stock to foundations. The foundation starting with A is to be built up in sequence from an ace to a king. The other foundations are similarly built up, but by twos, threes, and fours from 2, 3, and 4 until a king is reached. Here, a card of rank i may be used as a card of rank i + 13j for j ∈ {0, 1, 2, 3}. During the game, the player moves (i) the top card of the stock either onto a foundation or to the top of a tableau pile, or (ii) the top card of a tableau pile onto a foundation. We prove that the generalized version of Calculation Solitaire is NP-complete.

We study the complexity of finding the minimum number of face guards which can observe the whole surface of a polyhedral terrain. Here, a face guard is allowed to be placed on the faces of a terrain, and the guard can walk around on the allocated face. It is shown that finding the minimum number of face guards is NP-hard.

The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. A chromatic guarding is said to be conflict-free if at least one of the colors seen by every point in P is unique (i.e., each point in P is seen by some guard whose color appears exactly once among the guards visible to that point). In this paper, we consider vertex-to-point guarding, where the guards are placed on vertices of P, and they observe every point of the interior of P. The vertex-to-point conflict-free chromatic art gallery problem is to find a colored-guard set such that (i) guards are placed on P's vertices, and (ii) any point in P can see a guard of a unique color among all the visible guards. In this paper, it is shown that determining whether there exists a conflict-free chromatic vertex-guard set for a polygon with holes is NP-hard when the number of colors is k=2.

Chained Block is one of Nikoli's pencil puzzles. We study the computational complexity of Chained Block puzzles. It is shown that deciding whether a given instance of the Chained Block puzzle has a solution is NP-complete.