ASP-Complete Problems

CREATED: 200801070831 See paper by Yato and Seta 2003

• n-ASP ** given n solutions to a problem, find another one ** can be used to determine if the solution to a problem is unique
• Function problem pi(D,S,G) ** D is a problem instance ** S is the solution space ** G maps each element of D to a subset of S ** pi_d of pi given x in D, does x has a solution in S (decision version)
• pi is ASP-Complete => pi_d is NPC
• SAT, 3-SAT, Just 1 SAT, 1 in 3 SAT, Triangle partitioning, Latin squares, Sudoku
• Sudoku is ASP Complete => is also NP Complete