Determinacy-A_3是Co-NP完全的

THE DETERMINACY PROBLEM FOR MODEL A_3IS Co-NP-COMPLETE

群试(group testing)方法首先由Dorfman在第二次世界大战期间提出,当时是出于征兵验血的需要。现在,群试方法已应用于多门学科,诸如计算机科学,组合学及统计学等。可以把群试问题简述如下:设N是一个含有n个元素的集合,记为N={1,…,n},在N中有一些“坏”元素,我们试图通过一系列试验把全部“坏”元素找出来,如何使试验次数最少?我们把全体“坏”元素集称为样本,所有可能的样本形成样本空间。

The complexity of group testing is a long-standing open problem.Recently,Du and Ko studied some related problems which can explain the difficulty of group testing indirectly. One of such problems is called the determinacy problem on which they left some open problems.In this paper,we resolve one of these problems.