We discuss the problem of generating test instances for promised NP search problems. A technical framework is proposed for studying this problem, and it is shown that all known distNP-hard search problems are "complete" for test instance generation problems.
展开▼
