# 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