NP (复杂度)

✍ dations ◷ 2025-09-19 04:38:58 #复杂度类,计算机科学中未解决的问题

非决定性多项式集合(英语:non-deterministic polynomial,缩写:NP)是计算理论中最重要的集合之一。它包含P和NP-complete。P集合的问题即在多项式时间内可以找出解的决策性问题(decision problem)集合。注意NP包含P和NP-complete问题, 因此NP集合中有简单的问题和不容易快速得到解的难题。是一个计算机科学中知名的难题。

决策问题:一个决策问题(decision problem)是指其输出,只有“是”或“否”的问题。例如,搜索问题为询问 x 是否出现在一个集合 A 中?若有则输出“是”,否则输出“否”。
P集合: 当一个决策问题存在一个O(nk)时间复杂度的算法时,则称此问题落在P 的集合中。

有一些决策问题,人类目前尚无法将他们归入集合 P 中。为了思考这些问题,于是在一般算法可采用的功能上,扩增以下虚构的新指令。这些新指令虽然不存在于现实中,但是对探讨这些难题的性质及彼此的关系,有很大的帮助。以下是这些虚构的新指令:

1. choice(S):自集合 S 中,选出会导致正确解的一个元素。当集合 S 中无此元素时,则可任意选择一个元素。

2. failure():代表失败结束。

3. success():代表成功结束。
其中 choice(S)可以解释成,在求解的过程中,神奇地猜中集合 S 中其中一个元素,使其结果是成功的;并且这三个指令只需要 O(1)时间来运行。当然,choice(S) 是如何快速猜中的,在此是不需讨论的,因为毕竟它只是虚构的。在添加这些虚构功能后,所设计出的算法,被称为非决定性算法(non-deterministic algorithm);相较之下,原来一般的算法,就称为决定性算法(deterministic algorithm)。利用非决定性算法,我们定义出另一个集合 NP:

NP: 当一个决策问题存在一个O(nk)时间复杂度的算法时,则称此问题落在NP 的集合中。

满足问题 (satisfiability problem,简称 SAT),就是一个NP中的典型难题。

满足问题:令 x 1,x 2,…,x n 代表布尔变量(boolean variables)(其值非真(true)即假(false)的变量)。令-xi 代表 xi 的相反数(negation)。一个布尔公式是将一些布尔变量及其相反数利用而且(and)和或(or)所组成的表达式。满足问题是判断是否存在一种指定每个布尔变量真假值的方式,使得一个布尔公式为真。

输入:一个 n 个变量的布尔公式

例如: (-x 1∨ -x 2 ∨ x 3)∧ (x 1 ∨ x 4)∧(x 2 ∨ -x 1)

输出:是否存在一种指定每个布尔变量真假值的方式,使得此公式为真?例如: 是(当 x 1=真,x 2=真,x 3=真,x 4=真时,此公式为真)

利用满足问题可以定义出NP-hard和NP-complete。但是我们需要一个问题转换的概念。问题转换技巧,其所需要转换的时间皆需在多项式时间(即 O (nk))内完成。利用此多项式时间的转换,我们可以将 NP中的难题创建起一些有趣的关系。

问题转换:针对两个问题 A 和 B ,如果存在一个 O (nk)时间的(决定性)算法,将每一个问题 A 的输入转换成问题 B 的输入,使得问题 A 有解时,若且惟若,问题 B 有解。此关系被称为,问题 A 转换成(reduce to)问题 B ,可表示成 A ∝ B 。

一个问题 L 被称为是 NP-hard,若且惟若,满足问题转换成 L(即满足问题∝L)。满足问题是 NP 中的难题,而 NP-hard 的问题则是满足问题派生(转换)出来的。

一个问题 L 被称为是 NP-complete,若且惟若,L ∈NP 而且 L ∈NP-hard。

史蒂芬库克(Stephen Cook)证明了一个十分重要的性质:

性质(A):“任一个 NP 内的问题都可以,在多项式时间内,被转换成满足问题。”

性质(B):“任一个 NP 内的问题都可以,在多项式时间内,被转换成任一个 NP-complete 问题。”

性质(C):“任一个 NP 内的问题都可以,在多项式时间内,被转换成任一个 NP-hard 问题。”

性质(D):“满足问题在集合 P 中,当且仅当,P=NP。”

比如说,一个决策性问题:输入一个整数x, 请回答x是否为偶数(even number)。我们利用一个程序判断x除以2是否整除即可得到最后结果 。此程序是决定性算法, 并且其时间复杂度为O(1)=O(n0), 因此此问题落入P集合中。

再举一个例子,下面是满足问题的一个非决定性算法。

Algorithm satisfiability (E (x 1, … , xn ))

{Step 1: for i =1 to n do

xi ←choice (true, false) /*利用 choice 直接猜中 xi 的真假值*/

Step 2: if E (x 1, … , x n) is true then success () /*计算此布尔公式是否为真*/

    else failure ();
}


上述的非决定性算法的时间复杂度为O(n1)即代表满足问题落入NP集合中。

相关

  • 招魂术招魂术(英语:Necromancy)是指一种与死者灵魂沟通的巫术,在人类历史上已经存在一段很长的时间,通常和黑巫术或巫术有所关联。
  • 偏害共生片害共生,又称偏害共栖、偏害共生,是两种生物间共生关系的一种。片害共生有的时候也称为拮抗(antagonism)。在片害共生中,一种生物对另一种产生抑制、伤害作用,甚至杀死对方,但本身
  • 2013欧洲马肉冒充牛肉2013年欧洲马肉冒充牛肉事件是2013年一个发生于欧洲的食品丑闻。牛肉的食品已被证明含有马肉(含量高达100%)和其他未申报的肉类,如猪肉。据报导,2013年1月时,在英国和爱尔兰超市出
  • 巴布尔查希尔丁·穆罕默德·巴布尔(印地语:ज़हिर उद-दिन मुहम्मद बाबर;乌尔都语:ظہیر الدین محمد بابر‎‎;波斯语:ظهیرالدین محمد
  • 普莫诺蝎普莫诺蝎(学名:Pulmonoscorpius kirktonensis,字面意思为“会呼吸的蝎子”),又称为氧蝎、肺蝎,是一种已绝种的巨型蝎子,生活于石炭纪的维宪阶时期。化石曾发现于苏格兰的西洛锡安等
  • 李渔李渔(1611年9月13日-1680年2月12日),初名仙侣,后改名渔,字谪凡,号笠翁,后人常称之蟹仙。明末清初文学家、戏曲家、园林建筑设计师,曾经评定四大奇书,祖籍浙江省兰溪县(今浙江省兰溪市)夏
  • 皇六女清太祖第六女(1600年-1646年),名不详。清太祖努尔哈赤的六女儿,生母是庶妃嘉穆瑚觉罗氏。她和巴布泰、穆库什、巴布海、第五女为亲兄妹关系。万历四十一年 (1613年),下嫁孝慈高皇
  • 新兖铁路.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none
  • 克里斯蒂安 (菲斯滕贝格)克里斯蒂安·约阿西姆·马克西米利安·埃贡·尤斯比乌斯·玛利亚·胡贝图斯(Christian Joachim Maximilian Egon Hugo Eusebius Maria Hubertus;1977年11月22日-),出生于多瑙艾辛
  • 第三十乌尔皮乌斯军团第三十乌尔皮乌斯军团(英语:Legio XXX Ulpia Victrix)古罗马军队建制名称。由罗马帝国君主图拉真在达契亚战争时期于105年建立并存在至5世纪初。该军团曾先后参加达契亚战争和