Another Solution Problem (ASP)

---

In Complexity Theory, Another Solution problem denotes the class of problems that seek the existence of a second solution to NP search problems, given the existence of one solution. This class was first introduced by Ueda and Nagao., although ASP results for a number of problems had been in existence prior to that, e.g., Hamiltonian Circuit Problems

Formal definition

Given an instance $a$ of an NP search problem $A$, the problem ASP $A$ takes a solution to $a$ and asks if there is a second, different solution to $a$. For example, the ASP SAT problem takes in a boolean formula and a satisfying assignment of the formula, and asks if there is another distinct satisfying assignment of the same formula.

The problems in ASP are particularly interesting to puzzle designers. When designing a puzzle, we would often like to know whether the solution to the puzzle is unique or not, which is exactly the premise of ASP.

ASP reduction

ASP reductions are a special type of reductions that are essential in showing hardness for ASP problems. Formally, a problem $A$ is ASP reducible to another problem $B$ if,

• there exists a parsimonious reduction $R$ from $A$ to $B$
• there is a bijection between the solutions to an instance $x$ of $A$ and the solutions to the corresponding instance $R(x)$ of $B$ that can be computed in polynomial time.

Showing an ASP reduction provides us with crucial hardness information about the problems. For example,

• If ASP $B$ is in P (i.e., if it is solvable in polynomial time), ASP $A$ must be in P as well.
• If ASP $A$ is NP-hard, then ASP $B$ must be NP-hard as well.

ASP-hardness

A problem $A$ is known as ASP-hard if every NP search problem is ASP reducible to $A$. Consequently, if a problem is ASP-hard, then it is NP-hard as well.

A problem $A$ is known as ASP-complete if $A$ is an NP search problem itself and is NP-hard.

Examples

SAT

SAT is ASP-complete. SAT itself is an NP search problem, while the reduction given in Cook-Levin Theorem is an ASP reduction.

3SAT

3SAT asks whether a given boolean formula in 3-CNF form has a satisfying assignment. This problem can be shown to be ASP-complete via an ASP reduction from SAT.

1-in-3SAT

This problem is a variant of 3SAT, which asks whether a given boolean formula in 3-CNF form has a satisfying assignment where each clause contains exactly one true literal. This problem can be shown to be ASP-complete via two layers of ASP reductions from 3SAT.

Hamiltonian cycle

The problem of finding a Hamiltonian cycle in a planar directed max degree-3 graph is ASP-complete.

Slitherlink

Slitherlink is an example of an ASP-complete puzzle. The problem is to find a simple loop with no loose ends. This problem can be shown to be ASP-complete via an ASP reduction from the Hamiltonian cycle problem.

References

This article "Another Solution Problem (ASP)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Another Solution Problem (ASP). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---