Approximation of coNP Sets by NP-complete Sets and Its Applications

摘要

It is said that a set L1 in a class C1 is an approximation of a set L2 in a class C2 if L1 is a subset of L2. An approximation L1 is said to be optimal if there is no approximation L'1 such that L1 is contained in L'1 and L'1-L1 is infinite. When the class C_1=P and C_2=NP, it is known that there is no optimal approximation under a quite general condition unless P=NP. In this paper we discuss the case where C_1=the class of Np=complete sets and C_2=coNP. A similar result as above that shows the difficulty of the optimal approximation is obtained. Approximating coNP sets by NP-complete sets plays an important role in the efficient generation of test instances for combinatorial algorithms.