Melvin's digital garden

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

Links to this note