NP-难问题

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

此词条暂由彩云小译翻译，翻译字数共705，未经人工整理和审校，带来阅读不便，请见谅。

For a gentler introduction, see P versus NP problem.
文件:P np np-complete np-hard.svg
Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)

[[Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)]]

[ p，NP，NP 完全和 NP 难问题集的欧拉图。左边在 p ≠ NP 的假设下是有效的，而右边在 p = NP 的假设下是有效的(除非空语言及其补语永远不是 NP 完全)]]

In computational complexity theory, NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem.

In computational complexity theory, NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem.

在计算复杂性理论中，NP- 硬度(不确定的多项式时间硬度)是一类非正式问题的定义属性，这类问题“至少和 NP 中最难的问题一样难”。Np 难问题的一个简单例子是子集合加总问题。


A more precise specification is: a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, H模板:Ltr's solution can be used to solve L in polynomial time.[1][2] As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P [math]\displaystyle{ \neq }[/math] NP, it is unlikely that such an algorithm exists.[3]

A more precise specification is: a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, H's solution can be used to solve L in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P [math]\displaystyle{ \neq }[/math] NP, it is unlikely that such an algorithm exists.

一个更精确的定义是: 当 NP 中的每个问题 l 在多项式时间内都可以约化为 h 时，问题 h 是 NP 难的; 即假设 h 的解需要1个单位时间，h 的解可以在多项式时间内用来求解 l。因此，找到一个多项式时间算法来解决任何 NP 难问题，就可以给出 NP 问题的多项式时间算法。正如人们所怀疑的那样，p < math > neq </math > NP，这样的算法不太可能存在。


A common misconception is that the NP in "NP-hard" stands for "non-polynomial" when in fact it stands for "non-deterministic polynomial acceptable problems".[4] It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven.[5] Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class.[6]

A common misconception is that the NP in "NP-hard" stands for "non-polynomial" when in fact it stands for "non-deterministic polynomial acceptable problems". It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class.

一个常见的误解是“ NP 难”中的 NP 代表“非多项式” ，而实际上它代表“不确定的多项式可接受问题”。人们怀疑对于 np 难问题没有多项式时间算法，但是这一点还没有得到证明。此外，所有问题都可以在多项式时间内求解的 p 类包含在 NP 类中。


Definition

A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H.[1]:80

A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H. Informally, an algorithm can be thought of that calls such an oracle machine as a subroutine for solving H and solves L in polynomial time if the subroutine call takes only one step to compute.

当决策问题 h 对于 NP 中的每个问题 l 都存在多项式时间多次一次的非正式约简时，可以认为这样一种算法将这样一个预言机作为求解 h 的子程序，并且在子程序调用只需要一个步骤就可以计算的情况下用多项式时间求解 l。

An equivalent definition is to require that every problem L in NP can be solved in polynomial time by an oracle machine with an oracle for H.[7] Informally, an algorithm can be thought of that calls such an oracle machine as a subroutine for solving H and solves L in polynomial time if the subroutine call takes only one step to compute.


Another definition is to require that there be a polynomial-time reduction from an NP-complete problem G to H.

另一个定义是要求从 np 完全问题 g 到 h 有一个多项式时间图灵归约。

Another definition is to require that there be a polynomial-time reduction from an NP-complete problem G to H.[1]:91 As any problem L in NP reduces in polynomial time to G, L reduces in turn to H in polynomial time so this new definition implies the previous one. Awkwardly, it does not restrict the class NP-hard to decision problems, and it also includes search problems or optimization problems.


There are decision problems that are NP-hard but not NP-complete such as the halting problem. That is the problem which asks "given a program and its input, will it run forever?" That is a yes/no question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example, the Boolean satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, but the halting problem, in general, is undecidable. There are also NP-hard problems that are neither NP-complete nor Undecidable. For instance, the language of true quantified Boolean formulas is decidable in polynomial space, but not in non-deterministic polynomial time (unless NP = PSPACE).

有些决策问题是 np 难的，但不是 np 完全的，例如停机问题。这个问题就是“给定一个程序及其输入，它会永远运行下去吗? ”这是一个是/否的问题，也是一个决策问题。证明停机问题是 np 难问题而不是 np 完全问题是容易的。例如，布尔可满足性问题可以通过将其转换为一个图灵机的描述，该机尝试所有真值赋值，当它找到一个满足公式的时候就停止，否则就进入无限循环。由于 NP 中的所有问题在有限数目的运算中都是可判定的，所以停机问题在 NP 中不是可判定的，但是停机问题在一般情况下是不可判定的。还有一些 np 难题既不是 np 完全问题，也不是无法判定的问题。例如，真正量化的布尔公式的语言在 PSPACE 中是可判定的，但在不确定的多项式时间中是不可判定的(除非 NP = PSPACE)。

Consequences

If P ≠ NP, then NP-hard problems cannot be solved in polynomial time.


NP-hard problems do not have to be elements of the complexity class NP.

NP 难问题不一定是复杂类 NP 的元素。

Some NP-hard optimization problems can be polynomial-time approximated up to some constant approximation ratio (in particular, those in APX) or even up to any approximation ratio (those in PTAS or FPTAS).

As NP plays a central role in computational complexity, it is used as the basis of several classes:

由于 NP 在计算复杂性中起着核心作用，它被用作以下几类的基础:


NP: Class of computational decision problems for which a given yes-solution can be verified as a solution in polynomial time by a deterministic Turing machine (or solvable by a non-deterministic Turing machine in polynomial time).

NP: 一类计算决策问题，对于这类问题，一个给定的是-解可以被确定性的图灵机在多项式时间内验证为解(或者一个非确定型图灵机在多项式时间内可以解)。

Examples

NP-hard: Class of problems which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable.

NP 难题: 至少与 NP 中最难的问题一样难的一类问题。NP 难的问题不一定是 NP 的组成部分; 事实上，它们甚至可能不是可判定的。

An example of an NP-hard problem is the decision subset sum problem: given a set of integers, does any non-empty subset of them add up to zero? That is a decision problem and happens to be NP-complete. Another example of an NP-hard problem is the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph. This is commonly known as the traveling salesman problem.[8]

NP-complete: Class of decision problems which contains the hardest problems in NP. Each NP-complete problem has to be in NP.

NP 完全: 一类包含 NP 中最难问题的决策问题。每个 NP 完全问题都必须是 NP 完全问题。


NP-easy: At most as hard as NP, but not necessarily in NP.

NP-easy: 最多和 NP 一样难，但不一定是 NP。

There are decision problems that are NP-hard but not NP-complete such as the halting problem. That is the problem which asks "given a program and its input, will it run forever?" That is a yes/no question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example, the Boolean satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, but the halting problem, in general, is undecidable. There are also NP-hard problems that are neither NP-complete nor Undecidable. For instance, the language of true quantified Boolean formulas is decidable in polynomial space, but not in non-deterministic polynomial time (unless NP = PSPACE).[9]

NP-equivalent: Decision problems that are both NP-hard and NP-easy, but not necessarily in NP.

NP-equivalent: 决策问题既是 NP-hard 问题又是 NP-easy 问题，但不一定是 NP 问题。


NP-intermediate: If P and NP are different, then there exist decision problems in the region of NP that fall between P and the NP-complete problems. (If P and NP are the same class, then NP-intermediate problems do not exist because in this case every NP-complete problem would fall in P, and by definition, every problem in NP can be reduced to an NP-complete problem.)

NP- 中间: 如果 p 和 NP 是不同的，那么在 NP 区域中存在介于 p 和 NP- 完全问题之间的决策问题。(如果 p 和 NP 是同一类问题，那么 NP 中间问题就不存在，因为在这种情况下，每个 NP 完全问题都可以归结为 p，而且根据定义，NP 中的每个问题都可以归结为 NP 完全问题。)

NP-naming convention

NP-hard problems do not have to be elements of the complexity class NP.

As NP plays a central role in computational complexity, it is used as the basis of several classes:

NP-hard problems are often tackled with rules-based languages in areas including:

NP-hard 问题通常在以下领域用基于规则的语言来解决:

NP
Class of computational decision problems for which a given yes-solution can be verified as a solution in polynomial time by a deterministic Turing machine (or solvable by a non-deterministic Turing machine in polynomial time).
NP-hard
Class of problems which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable.
NP-complete
Class of decision problems which contains the hardest problems in NP. Each NP-complete problem has to be in NP.
NP-easy
At most as hard as NP, but not necessarily in NP.
NP-equivalent
Decision problems that are both NP-hard and NP-easy, but not necessarily in NP.
NP-intermediate
If P and NP are different, then there exist decision problems in the region of NP that fall between P and the NP-complete problems. (If P and NP are the same class, then NP-intermediate problems do not exist because in this case every NP-complete problem would fall in P, and by definition, every problem in NP can be reduced to an NP-complete problem.)


Application areas

NP-hard problems are often tackled with rules-based languages in areas including:

  • Process monitoring and control
  • Rosters or schedules
  • Routing/vehicle routing


Category:Complexity classes

类别: 复杂性类


This page was moved from wikipedia:en:NP-hardness. Its edit history can be viewed at NP-难问题/edithistory

  1. ↑ 1.0 1.1 1.2 Leeuwen, Jan van, ed. (1998). Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier. ISBN 0262720140. OCLC 247934368. 
  2. ↑ Knuth, Donald (1974). "Postscript about NP-hard problems". ACM SIGACT News. 6 (2): 15–16. doi:10.1145/1008304.1008305.
  3. ↑ Daniel Pierre Bovet; Pierluigi Crescenzi (1994). Introduction to the Theory of Complexity. Prentice Hall. p. 69. ISBN 0-13-915380-2. 
  4. ↑ "P and NP". www.cs.uky.edu. Archived from the original on 2016-09-19. Retrieved 2016-09-25.
  5. ↑ "Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP". www.scottaaronson.com. Retrieved 2016-09-25.
  6. ↑ "PHYS771 Lecture 6: P, NP, and Friends". www.scottaaronson.com. Retrieved 2016-09-25.
  7. ↑ V. J. Rayward-Smith (1986). A First Course in Computability. Blackwell. p. 159. ISBN 0-632-01307-9. 
  8. ↑ Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0-471-90413-9.
  9. ↑ More precisely, this language is PSPACE-complete; see, for example, Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 189, ISBN 9783540210450.
取自“https://wiki.swarma.org/index.php?title=NP-难问题&oldid=17160”