在计算复杂度理论上,反NP类是复杂度类的其中一类。
定义
一个问题
是反NP的成员,若且唯若,它的补全
必定是在复杂度NP;用数学符号来写,
。
简单来说,反NP复杂度,是高效率而又可核实地证明命题为错的组群,当中的佼佼者是立即找到反例存在。
其中一个NP完全问题的例子是子集合加总问题:给一个整数集合,问是否存在某个非空子集中的数字和为0? 例:给定集合{−7, −3, −2, 5, 8},答案是是,因为子集合{−3, −2, 5}的数字和是0。
补全问题在反NP中就会要求:给有限的整数集,是否每个非空子集之总和皆不为0?你的证明只要必须给出事例,叙述"没有"指定求和到零的一个非空子集,而这证明必须可以在合理时间内验证。
与其他复杂度的关系
复杂度P,是多项式时间可解的问题集合,是一个NP和反NP的子集。P通常认定是一个在此两类别下的严格子集(但无法验证是落在两个集合的哪一边)。NP和反NP通常认为是不相等的。如果那样,NP完全问题将不会落在反NP问题中,且反NP完全问题将不会落在NP中。
本问题可由下述步骤粗略证明:假设有个NP完全问题
处于反NP问题的集合中,由于所有NP问题可被变换成
问题,因此我们可以为所有NP问题建造一个可在多项式时间判定其补性质的非确定型图灵机,意即NP是反NP的子集。因此NP问题的补集合是一个反NP问题的补集合的子集,意即反NP是NP的子集。由于我们已知NP是反NP的子集,因此表示这两个集合是一样的,这证明了没有反NP完全问题可在NP类之中的性质是对称的(Symmetrical)。
用数学符号严格证明:假设一个问题
是NP完全,
,若且唯若
。以下的证明是不能从以上文字直接看得出:
- 若
,![{\displaystyle {\mathcal {X}}\in \mathbf {NP} \Rightarrow {\mathcal {X}}\in \mathbf {CoNP} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e64826370f9c979c3a062e626af8bf60e1c6c2e1)
:如果
。很明显地,若
是NP完全,自然
是NP难,
,所以
。但
亦即代表
,所以
,最终
。
:![{\displaystyle {\mathcal {X}}\in \mathbf {CoNP} \Rightarrow {\mathcal {X}}^{\mathrm {C} }\in \mathbf {NP} \Rightarrow {\mathcal {X}}^{\mathrm {C} }\in \mathbf {CoNP} \Rightarrow ({\mathcal {X}}^{\mathrm {C} })^{\mathrm {C} }={\mathcal {X}}\in \mathbf {NP} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4cb05a497c4579423c6c6b9ea5f23e90e40927a)
如果一个问题可被证同时为NP与反NP,则通常我们将会视作本问题不是NP完全命题的强力假设(若非如此,则NP相等于反NP)。
应用
一个同时在NP与反NP集合的有名问题是整数分解:给两个正整数m与n,决定m是否有小于n且大于1的因数。
第一个问题的方法很清晰:如果m的确存在一个满足条件的因子,则长除法即可验证;另一个问题的方法就困难且精妙多了:你必须将m的所有质数因子列出,并为每个因子提供质数性质的证明。
整数因子分解常与质数性质问题混淆在一起,整数因子化据信是NP或反NP,而质数问题落在类别P[1]。
文内注释
参考资料
外部链接
|
---|
| 易解复杂度类 | | |
---|
| 怀疑难解复杂度类 | |
---|
| 难解复杂度类 | |
---|
| 复杂度类的谱系 | |
---|
| 相关复杂度族 | |
---|
|