Feeds:
Posts
Comments

Archive for November, 2008

遭遇NP-Hardness

BBS算法版上时不时的会有人问"一个整数集合,划分成两部分,使得两部分的和的差最小"之类的问题,而且说是面试题目。我想这样的面试官也太不厚道,要是不知道NP理论的面试者岂不是要想算法想得很郁闷。没想到我也在面试中遭遇NP-Hard问题了,不过这个问题没那么裸。
说一个测试数据集U,每次可以任取一个U的子集作为一次O(1)时间测试的输入,测试的结果可能fail或者不fail。测试的结果总是相容的,即子集A是子集B的子集,如果A测试fail那么B测试一定也fail。问题是找到一个最小的子集使得测试fail掉。如果最小的子集只有1个元素,二分就行了;两个元素的情况也可以二分。最小集元素多了就不好办了。我当时想P算法想了好一会,最后觉得应该是NP-Hard的,于是跟面试官说了,然后被要求给个证明。当时把子集和问题归结到这个问题,归结的过程很简单。面试结束后发现,我给的那个reduction错得很离谱,近乎扯淡,面试官当时竟然没发现,而且貌似还对我的证明很赞许。下来又想了下,问题确实是NP-Hard的,证明也不难,可以把Set Cover归结到这个问题。对一个Set Cover问题实例(U, {S1,S2,…,Sn}),构造测试程序,对于输入子集A={ S’, S”, …},测试返回fail当且仅当A覆盖全集U。显然这个测试可以在多项式时间内完成,而且Set Cover的最小覆盖集正好对应{S1,S2,…,Sn}的最小fail子集。

Advertisements

Read Full Post »