In this paper, we consider the problem of inferring a Boolean network (BN) from a given set of singleton attractors, where it is required that the resulting BN has the same set of singleton attractors as the given one. We show that the problem can be solved in linear time if the number of singleton attractors is at most two and each Boolean function is restricted to be a conjunction or disjunction of literals. We also show that the problem can be solved in polynomial time if more general Boolean functions can be used. In addition to the inference problem, we study two network completion problems from a given set of singleton attractors: adding the minimum number of edges to a given network, and determining Boolean functions to all nodes when only network structure of a BN is given. In particular, we show that the latter problem cannot be solved in polynomial time unless P=NP, by means of a polynomial-time Turing reduction from the complement of the another solution problem for the Boolean satisfiability problem.

Generalized Tsume-Shogi (GTS) is Tsume-Shogi on the board of size n n for arbitrary n. The problem to decide the existence of a winning sequence of moves (where the attacker must always check) on an instance of GTS was proved to be exptime-complete by Yokota et al. (2000). This paper considers the complexity of yozume problem of GTS, which is, roughly speaking, the problem whether a given position of GTS has a winning sequence other than given sequences (though the actual rule of yozume is more complicated). The detection of yozume is an important issue in designing Tsume-Shogi problems, since the modern designing rule strongly prohibits it. We define a function problem of GTS appropriately to formulate yozume problem as its Another Solution Problem (ASP; the problem to decide the existence of solutions other than given ones). Moreover, we extend the existing framework for investigating ASPs so that it can be applied to exptime-complete problems. In particular, since the decision of correctness of given winning sequences is not easy, we establish a framework to treat ASP of function problems with promises. On the basis of these results, we prove that the decision version of yozume problem of GTS is exptime-complete as a promise problem using the existing reduction which was constructed by Yokota et al. to prove the exptime-completeness of GTS.

The Another Solution Problem (ASP) of a problem is the following problem: for a given instance x of and a solution s to it, find a solution to x other than s. The notion of ASP as a new class of problems was first introduced by Ueda and Nagao. They also pointed out that parsimonious reductions which allow polynomial-time transformation of solutions can derive the NP-completeness of ASP of a certain problem from that of ASP of another. In this paper we consider n-ASP, the problem to find another solution when n solutions are given, and formalize it to investigate its characteristics. In particular we consider ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above. The complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Cross Sum, and Number Place. Since ASP-completeness implies NP-completeness, these results can be regarded as new results of NP-completeness proof of puzzles.