Approximation of coNP sets by NP-complete sets and its applications
Shuichi Miyazaki, Kazuo Iwama · Systems and Computers in Japan · 1999
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⊂L′1 and L′1−L1 is infinite. When the class C1 = P and C2 = 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 C1 = the class of NP-complete sets and C2 = 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. © 1999 Scripta Technica, Syst Comp Jpn, 30(7): 47–54, 1999