NP完全

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

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

模板:Confusing

文件:3SAT 17 svg.svg
The Boolean satisfiability problem (SAT) asks to determine if a propositional formula (example depicted) can be made true by an appropriate assignment of truth values to its variables. While it is easy to verify whether a given assignment renders the formula true,[1] no essentially faster method to find a satisfying assignment is known than to try all assignments in succession. Cook and Levin proved that each easy-to-verify problem can be solved as fast as SAT, which is hence NP-complete.

In computational complexity theory, a problem is NP-complete when:

  1. it is a problem for which the correctness of each solution can be verified quickly and a brute-force search algorithm can actually find a solution by trying all possible solutions.
  2. the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense it is the hardest of the problems to which solutions can be verified quickly so that if we could actually find solutions of some NP-Complete problem quickly, we could quickly find the solutions of every other problem to which a solution once given is easy to check.

The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. "Complete" refers to the property of being able to simulate everything in the same complexity class.

In computational complexity theory, a problem is NP-complete when:

  1. it is a problem for which the correctness of each solution can be verified quickly and a brute-force search algorithm can actually find a solution by trying all possible solutions.
  2. the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense it is the hardest of the problems to which solutions can be verified quickly so that if we could actually find solutions of some NP-Complete problem quickly, we could quickly find the solutions of every other problem to which a solution once given is easy to check.

The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. "Complete" refers to the property of being able to simulate everything in the same complexity class.

在计算复杂性理论中,一个问题是 np 完全的,当: # 这是一个问题,每个解的正确性都可以被快速验证,而暴力搜索法算法实际上可以通过尝试所有可能的解来找到解。# 这个问题可以用来模拟其他问题,我们可以很快地验证一个解决方案是正确的。从这个意义上说,这是最难的问题,其解决方案可以迅速得到验证,以便如果我们能够真正快速地找到一些 np 完全问题的解决方案,我们就能够快速地找到其他所有问题的解决方案,而一旦给出一个解决方案就很容易验证。名称“ np 完全”是“不确定的多项式时间完全”的缩写。在这个名称中,“不确定性”指的是不确定的图灵机,这是一种数学形式化的暴力搜索法算法的思想。多项式时间是指一个确定性算法用来检查一个解决方案的时间,或者一个不确定的图灵机执行整个搜索的时间。“完成”指的是能够在相同的复杂性类中模拟所有事物的特性。

More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time),[2] such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP, an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. Conversely, a problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC.

More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP, an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. Conversely, a problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC.

更确切地说,问题的每个输入都应与一组多项式长度的解相关联,这些解的有效性可以很快(在多项式时间内)检验,这样,如果解集是非空的,任何输入的输出都是”是”,如果解集是空的,输出就是”否”。这种形式的问题的复杂类称为 NP,是“ NP”的缩写。如果 NP 中的任何问题都可以在多项式时间内转化为 NP 难问题,即使这个问题不一定是 NP 难问题。反之,如果一个问题同时在 NP 和 NP 困难中,则该问题是 NP 完全问题。NP 完全问题是 NP 完全问题中最困难的问题。如果某个 NP 完全问题具有多项式时间算法,则 NP 完全问题都具有多项式时间算法。Np- 完全问题的集合通常用 NP-C 或 NPC 来表示。

Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the fundamental unsolved problems in computer science today.

Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the fundamental unsolved problems in computer science today.

虽然 np 完全问题的解决方案可以“快速”验证,但是没有已知的方法可以快速找到解决方案。也就是说,随着问题规模的增大,使用任何当前已知算法解决问题所需的时间迅速增加。因此,确定是否有可能快速解决这些问题,即所谓的 P/NP问题,是当今计算机科学尚未解决的基本问题之一。

While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms.

While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms.

虽然计算 np 完全问题的解的方法仍然没有被发现,但计算机科学家和程序员仍然经常遇到 np 完全问题。Np 完全问题通常采用启发式方法和近似算法求解。

Overview

NP-complete problems are in NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a non-deterministic Turing machine. A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time.

NP-complete problems are in NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a non-deterministic Turing machine. A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time.

= = Overview = = NP 完全问题在 NP 中,所有的决策问题的解可以在多项式时间内得到验证; NP 可以等价地定义为在多项式时间内可以在非确定型图灵机上得到解决的决策问题的集合。如果 NP 中的其他问题都能在多项式时间内转化(或简化)为 p,则 NP 中的问题 p 是 NP 完全的。

It is not known whether every problem in NP can be quickly solved—this is called the P versus NP problem. But if any NP-complete problem can be solved quickly, then every problem in NP can, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every NP-complete problem (that is, it can be reduced in polynomial time). Because of this, it is often said that NP-complete problems are harder or more difficult than NP problems in general.

It is not known whether every problem in NP can be quickly solved—this is called the P versus NP problem. But if any NP-complete problem can be solved quickly, then every problem in NP can, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every NP-complete problem (that is, it can be reduced in polynomial time). Because of this, it is often said that NP-complete problems are harder or more difficult than NP problems in general.

目前尚不清楚 NP 中的所有问题是否都能迅速得到解决---- 这就是所谓的 P/NP问题。但是,如果任何一个 NP 完全问题都可以快速求解,那么 NP 中的任何问题都可以快速求解,因为 NP 完全问题的定义表明,NP 中的任何问题都必须快速地可约为任何一个 NP 完全问题(即可以在多项式时间内进行约化)。正因为如此,人们常说 NP- 完全问题比一般的 NP 问题更难或更难。

Formal definition

A decision problem [math]\displaystyle{ \scriptstyle C }[/math] is NP-complete if:

  1. [math]\displaystyle{ \scriptstyle C }[/math] is in NP, and
  2. Every problem in NP is reducible to [math]\displaystyle{ \scriptstyle C }[/math] in polynomial time.[3]

A decision problem \scriptstyle C is NP-complete if:

  1. \scriptstyle C is in NP, and
  2. Every problem in NP is reducible to \scriptstyle C in polynomial time.

一个决策问题 scriptstyle c 是 NP- 完全的,如果: # scriptstyle c 在 NP 中,# NP 中的每个问题在多项式时间内都可归约为 scriptstyle c。

[math]\displaystyle{ \scriptstyle C }[/math] can be shown to be in NP by demonstrating that a candidate solution to [math]\displaystyle{ \scriptstyle C }[/math] can be verified in polynomial time.

\scriptstyle C can be shown to be in NP by demonstrating that a candidate solution to \scriptstyle C can be verified in polynomial time.

脚本风格 c 可以通过证明一个候选解决方案的脚本风格 c 可以证明是在 NP 的多项式时间。

Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1.[4]

Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1.

请注意,满足条件2的问题称为 np 难问题,无论它是否满足条件1。

A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for [math]\displaystyle{ \scriptstyle C }[/math], we could solve all problems in NP in polynomial time.

A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for \scriptstyle C, we could solve all problems in NP in polynomial time.

这个定义的一个结果是,如果我们有一个多项式时间算法(在一个 UTM,或任何其他图灵等价的抽象机)的脚本风格的 c,我们可以在多项式时间在 NP 解决所有问题。

Background

文件: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, and in general, not every problem in P or NP is NP-complete)

The concept of NP-completeness was introduced in 1971 (see Cook–Levin theorem), though the term NP-complete was introduced later. At the 1971 STOC conference, there was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine. John Hopcroft brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or the other. This is known as "the question of whether P=NP".

The concept of NP-completeness was introduced in 1971 (see Cook–Levin theorem), though the term NP-complete was introduced later. At the 1971 STOC conference, there was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine. John Hopcroft brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or the other. This is known as "the question of whether P=NP".

Np- 完全性的概念是在1971年引入的(见 Cook-Levin 定理) ,不过 np- 完全性这个术语是后来才引入的。在1971年的 STOC 会议上,计算机科学家们就 np 完全问题能否在确定性图灵机上用多项式时间解决展开了激烈的争论。约翰 · 霍普克罗夫特使与会者达成共识,即 np 完全问题能否在多项式时间内得到解决的问题应该推迟到以后解决,因为没有人能以这样或那样的方式为自己的主张提供任何正式的证明。这就是所谓的“ p = NP”问题。

Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics. The Clay Mathematics Institute is offering a US$1 million reward to anyone who has a formal proof that P=NP or that P≠NP.

Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics. The Clay Mathematics Institute is offering a US$1 million reward to anyone who has a formal proof that P=NP or that P≠NP.

到目前为止,还没有人能够确切地确定 np- 完全问题是否实际上可以在多项式时间内解决,这使得 np- 完全问题成为数学界尚未解决的重大问题之一。美国克雷数学研究所将悬赏100万美元给任何有正式证据证明 p = NP 或 p 不等于 NP 的人。

The Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete. In 1972, Richard Karp proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems); thus there is a class of NP-complete problems (besides the Boolean satisfiability problem). Since the original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in Garey and Johnson's 1979 book Computers and Intractability: A Guide to the Theory of NP-Completeness.[5]

The Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete. In 1972, Richard Karp proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems); thus there is a class of NP-complete problems (besides the Boolean satisfiability problem). Since the original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in Garey and Johnson's 1979 book Computers and Intractability: A Guide to the Theory of NP-Completeness.

Cook-Levin 定理指出布尔可满足性问题是 np 完全的。1972年,Richard Karp 证明了其他几个问题也是 np 完全问题(参见 Karp 的21个 np 完全问题) ,因此存在一类 np 完全问题(除了布尔可满足性问题问题)。自从最初的结果以来,通过对以前被证明是 np 完全的其他问题进行约简,数千个其他问题已被证明是 np 完全问题,其中许多问题收集在 Garey 和约翰逊1979年出版的《计算机和难解性: np 完全性理论指南》一书中。

NP-complete problems

文件:Relative NPC chart.svg
Some NP-complete problems, indicating the reductions typically used to prove their NP-completeness

An interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices. Consider these two problems:

  • Graph Isomorphism: Is graph G1 isomorphic to graph G2?
  • Subgraph Isomorphism: Is graph G1 isomorphic to a subgraph of graph G2?

An interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices. Consider these two problems:

  • Graph Isomorphism: Is graph G1 isomorphic to graph G2?
  • Subgraph Isomorphism: Is graph G1 isomorphic to a subgraph of graph G2?

一个有趣的例子是图同构问题,这是一个确定两个图之间是否存在图同构的图论问题。两个图是同构的,如果一个图可以简单地通过重命名顶点变换成另一个图。考虑这两个问题:

  • 图同构: 图 g1与图 g2同构吗?
  • 子图同构: 图 g1是否同构于图 g2的子图?

The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be hard, but is not thought to be NP-complete. These are called NP-Intermediate problems and exist if and only if P≠NP.

The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be hard, but is not thought to be NP-complete. These are called NP-Intermediate problems and exist if and only if P≠NP.

子图同构问题是 np 完全问题。图的同构问题虽然是 NP 问题,但在 p 和 NP 完全中都被怀疑是非完全的。这是一个被认为是困难的问题的例子,但是不被认为是 np 完全的。这些问题称为 NP 中间问题,当且仅当 p ≠ NP 时存在。

The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. The list below contains some well-known problems that are NP-complete when expressed as decision problems.

The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. The list below contains some well-known problems that are NP-complete when expressed as decision problems.

  • Boolean satisfiability problem (SAT)
  • Knapsack problem
  • Hamiltonian path problem
  • Travelling salesman problem (decision version)
  • Subgraph isomorphism problem
  • Subset sum problem
  • Clique problem
  • Vertex cover problem
  • Independent set problem
  • Dominating set problem
  • Graph coloring problem


证明某个新问题是 NP- 完全问题的最简便方法是先证明它是 NP 完全问题,然后将某个已知的 NP- 完全问题化为 NP 完全问题。因此,了解各种 np 完全问题是很有用的。下面的列表包含一些众所周知的问题,这些问题在表示为决策问题时是 np 完整的。

  • 布尔可满足性问题
  • 背包问题
  • 哈密顿路径问题
  • 旅行推销员问题(决策版本)
  • 子图同构问题
  • 子集合加总问题
  • 团问题
  • 覆盖
  • 独立集问题
  • 控制集问题
  • 图着色问题

To the right is a diagram of some of the problems and the reductions typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. Note that this diagram is misleading as a description of the mathematical relationship between these problems, as there exists a polynomial-time reduction between any two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest.

To the right is a diagram of some of the problems and the reductions typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. Note that this diagram is misleading as a description of the mathematical relationship between these problems, as there exists a polynomial-time reduction between any two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest.

右边是一些问题和通常用来证明其 np 完备性的约化图。在这个图表中,问题从下到上被简化了。请注意,这个图表作为这些问题之间的数学关系的描述是有误导性的,因为任何两个 np 完全问题之间都存在一个多项式时间图灵归约,但它表明在哪里证明这个多项式时间图灵归约是最容易的。

There is often only a small difference between a problem in P and an NP-complete problem. For example, the 3-satisfiability problem, a restriction of the boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2-satisfiability problem is in P (specifically, NL-complete), and the slightly more general max. 2-sat. problem is again NP-complete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted to planar graphs. Determining if a graph is a cycle or is bipartite is very easy (in L), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete.

There is often only a small difference between a problem in P and an NP-complete problem. For example, the 3-satisfiability problem, a restriction of the boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2-satisfiability problem is in P (specifically, NL-complete), and the slightly more general max. 2-sat. problem is again NP-complete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted to planar graphs. Determining if a graph is a cycle or is bipartite is very easy (in L), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete.

P 中的问题和 np 完全问题之间通常只有很小的差别。例如,3- 可满足性问题,一个布尔可满足性问题的限制,仍然是 np 完全,而稍微限制的2- 可满足性问题是在 p (具体地说,NL-complete) ,和稍微更一般的最大。2-sat.问题也是 np 完全问题。决定一个图是否可以用2种颜色着色的方法是 p,而用3种颜色的方法是 np 完全的,即使只限于平面图也是如此。确定一个图是圈还是二部图是非常容易的(在 l 中) ,但是找到一个最大二部图或最大圈子图是 np 完全的。在最优解的任意固定百分比范围内,背包问题的解可以在多项式时间内计算出来,但是找到最优解是 np 完全的。

Solving NP-complete problems

At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size, in fact 模板:Clarify span for some [math]\displaystyle{ k\gt 0 }[/math] and it is unknown whether there are any faster algorithms.

At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size, in fact for some k>0 and it is unknown whether there are any faster algorithms.

= = 解 np 完全问题 = = = 目前,所有已知的 np 完全问题的算法都需要输入大小为超多项式的时间,实际上对于某些 k > 0,是否存在更快的算法还不得而知。

The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:

  • Approximation: Instead of searching for an optimal solution, search for a solution that is at most a factor from an optimal one.
  • Randomization: Use randomness to get a faster average running time, and allow the algorithm to fail with some small probability. Note: The Monte Carlo method is not an example of an efficient algorithm in this specific sense, although evolutionary approaches like Genetic algorithms may be.
  • Restriction: By restricting the structure of the input (e.g., to planar graphs), faster algorithms are usually possible.
  • Parameterization: Often there are fast algorithms if certain parameters of the input are fixed.
  • Heuristic: An algorithm that works "reasonably well" in many cases, but for which there is no proof that it is both always fast and always produces a good result. Metaheuristic approaches are often used.

The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms:

  • Approximation: Instead of searching for an optimal solution, search for a solution that is at most a factor from an optimal one.
  • Randomization: Use randomness to get a faster average running time, and allow the algorithm to fail with some small probability. Note: The Monte Carlo method is not an example of an efficient algorithm in this specific sense, although evolutionary approaches like Genetic algorithms may be.
  • Restriction: By restricting the structure of the input (e.g., to planar graphs), faster algorithms are usually possible.
  • Parameterization: Often there are fast algorithms if certain parameters of the input are fixed.
  • Heuristic: An algorithm that works "reasonably well" in many cases, but for which there is no proof that it is both always fast and always produces a good result. Metaheuristic approaches are often used.

下面的技术可以用来解决一般的计算问题,而且它们通常产生更快的算法:

  • 逼近: 不是寻找最佳解决方案,而是从最佳解决方案中寻找最多是一个因素的解决方案。
  • 随机化: 使用随机性来获得更快的平均运行时间,并允许算法以一些小概率失败。注意: 尽管遗传算法这样的进化方法可能是有效的,但在这个特定意义上,蒙特卡罗方法算法并不是一个有效算法的例子。
  • 限制: 通过限制输入结构(例如,限制为平面图) ,通常可以实现更快的算法。
  • 参量化: 如果输入的某些参数是固定的,通常会有快速算法。
  • 启发式算法: 在许多情况下工作“相当好”,但是没有证据表明它总是快速的,并且总是产生良好的结果。经常使用元启发式方法。

One example of a heuristic algorithm is a suboptimal [math]\displaystyle{ \scriptstyle O(n\log n) }[/math] greedy coloring algorithm used for graph coloring during the register allocation phase of some compilers, a technique called graph-coloring global register allocation. Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application.

One example of a heuristic algorithm is a suboptimal \scriptstyle O(n\log n) greedy coloring algorithm used for graph coloring during the register allocation phase of some compilers, a technique called graph-coloring global register allocation. Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application.

启发式算法的一个例子是,在某些编译器的寄存器分配阶段,用于图着色的次优 scriptstyle o (n log n)贪婪着色算法,称为图着色全局寄存器分配技术。每个顶点都是一个变量,边在同时使用的变量之间绘制,颜色表示赋予每个变量的寄存器。因为大多数 RISC 机器都有相当多的通用寄存器,所以即使是一种启发式方法对于这个应用程序也是有效的。

Completeness under different types of reduction

In the definition of NP-complete given above, the term reduction was used in the technical meaning of a polynomial-time many-one reduction.

In the definition of NP-complete given above, the term reduction was used in the technical meaning of a polynomial-time many-one reduction.

= = = 不同类型归约的完备性 = = 在上文给出的 np 完备定义中,归约一词用于多项式多次一次归约的技术含义。

Another type of reduction is polynomial-time Turing reduction. A problem [math]\displaystyle{ \scriptstyle X }[/math] is polynomial-time Turing-reducible to a problem [math]\displaystyle{ \scriptstyle Y }[/math] if, given a subroutine that solves [math]\displaystyle{ \scriptstyle Y }[/math] in polynomial time, one could write a program that calls this subroutine and solves [math]\displaystyle{ \scriptstyle X }[/math] in polynomial time. This contrasts with many-one reducibility, which has the restriction that the program can only call the subroutine once, and the return value of the subroutine must be the return value of the program.

Another type of reduction is polynomial-time Turing reduction. A problem \scriptstyle X is polynomial-time Turing-reducible to a problem \scriptstyle Y if, given a subroutine that solves \scriptstyle Y in polynomial time, one could write a program that calls this subroutine and solves \scriptstyle X in polynomial time. This contrasts with many-one reducibility, which has the restriction that the program can only call the subroutine once, and the return value of the subroutine must be the return value of the program.

另一种类型的还原是多项式时间图灵还原。问题 scriptstyle x 是多项式时间的 Turing-reducible to a problem scriptstyle y,如果给定一个在多项式时间内解决 scriptstyle y 的子例程,可以编写一个调用这个子例程并在多项式时间内解决 scriptstyle x 的程序。这与多一可约性相反,多一可约性有一个限制,即程序只能调用子程序一次,子程序的返回值必须是程序的返回值。

If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of problems won't be smaller than NP-complete; it is an open question whether it will be any larger.

If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of problems won't be smaller than NP-complete; it is an open question whether it will be any larger.

如果一个人定义了类似于 np 完全的图灵约化而不是多个一的约化,那么得到的问题集不会小于 np 完全问题集,它是否会更大还是个未知数。

Another type of reduction that is also often used to define NP-completeness is the logarithmic-space many-one reduction which is a many-one reduction that can be computed with only a logarithmic amount of space. Since every computation that can be done in logarithmic space can also be done in polynomial time it follows that if there is a logarithmic-space many-one reduction then there is also a polynomial-time many-one reduction. This type of reduction is more refined than the more usual polynomial-time many-one reductions and it allows us to distinguish more classes such as P-complete. Whether under these types of reductions the definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions. All currently known NP-complete problems remain NP-complete even under much weaker reductions such as [math]\displaystyle{ AC_0 }[/math] reductions and [math]\displaystyle{ NC_0 }[/math] reductions. Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections.[6] It is known, however, that AC0 reductions define a strictly smaller class than polynomial-time reductions.[7]

Another type of reduction that is also often used to define NP-completeness is the logarithmic-space many-one reduction which is a many-one reduction that can be computed with only a logarithmic amount of space. Since every computation that can be done in logarithmic space can also be done in polynomial time it follows that if there is a logarithmic-space many-one reduction then there is also a polynomial-time many-one reduction. This type of reduction is more refined than the more usual polynomial-time many-one reductions and it allows us to distinguish more classes such as P-complete. Whether under these types of reductions the definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions. All currently known NP-complete problems remain NP-complete even under much weaker reductions such as AC_0 reductions and NC_0 reductions. Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections. It is known, however, that AC0 reductions define a strictly smaller class than polynomial-time reductions.


另一种常用于定义 np- 完全性的约简类型是对数空间多一约简,这是一种只能用对数空间量计算的多一约简。由于在对数空间中可以进行的每一次计算也可以在多项式时间内进行,因此,如果存在对数空间多一次还原,那么也存在多项式时间多一次还原。这种类型的约简比通常的多项式时间多次一次约简更精确,它使我们能够区分更多的类,如 p 完全。在这些类型的约简下,np 完全变更的定义是否仍然是一个悬而未决的问题。当前已知的所有 np 完全问题在对数空间约简下都是 np 完全问题。目前所有已知的 np 完全问题仍然是 np 完全问题,即使在较弱的约简,如 AC _ 0约简和 NC _ 0约简下。一些 np 完全问题,如 SAT,即使在多对数时间预测下也是完全的。然而,众所周知,AC < sup > 0 减少定义了一个严格比多项式时间减少更小的类。

Naming

According to Donald Knuth, the name "NP-complete" was popularized by Alfred Aho, John Hopcroft and Jeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with the results of a poll he had conducted of the theoretical computer science community.[8] Other suggestions made in the poll[9] included "Herculean", "formidable", Steiglitz's "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way the P versus NP problem went, could stand for "模板:Sic exponential time" or "previously exponential time".[10]

According to Donald Knuth, the name "NP-complete" was popularized by Alfred Aho, John Hopcroft and Jeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with the results of a poll he had conducted of the theoretical computer science community.Don Knuth, Tracy Larrabee, and Paul M. Roberts, Mathematical Writing § 25, MAA Notes No. 14, MAA, 1989 (also Stanford Technical Report, 1987). Other suggestions made in the poll included "Herculean", "formidable", Steiglitz's "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way the P versus NP problem went, could stand for " exponential time" or "previously exponential time".See the poll, or .

= = 命名 = = 按照唐纳德 · 克努斯的说法,阿尔弗雷德 · 阿霍、约翰 · 霍普克罗夫特和杰弗里 · 乌尔曼在他们著名的教科书《计算机算法的设计与分析》中推广了“ np 完成”这个名字。他报告说,根据他在理论计算机科学界进行的民意调查结果,他们引入了这本书的长条形证明(从“多项式-完整”)的变化。和 Paul m. Roberts,《数学写作25》 ,MAA 注释 No。14,MAA,1989(也是斯坦福技术报告,1987)。调查还提出了其他一些建议,包括“大力士”、“强大”、 Steiglitz 为了纪念 Cook 而创作的“冷酷无情”,以及 Shen Lin 的首字母缩略词“ PET”,意思是“可能是 EXPTIME”,但取决于 P/NP问题的走向,它可以代表“ EXPTIME”或“以前的 EXPTIME”。看看投票,或者。

Common misconceptions

The following misconceptions are frequent.[11]

  • "NP-complete problems are the most difficult known problems." Since NP-complete problems are in NP, their running time is at most exponential. However, some problems have been proven to require more time, for example Presburger arithmetic. Of some problems, it has even been proven that they can never be solved at all, for example the Halting problem.
  • "NP-complete problems are difficult because there are so many different solutions." On the one hand, there are many problems that have a solution space just as large, but can be solved in polynomial time (for example minimum spanning tree). On the other hand, there are NP-problems with at most one solution that are NP-hard under randomized polynomial-time reduction (see Valiant–Vazirani theorem).
  • "Solving NP-complete problems requires exponential time." First, this would imply P ≠ NP, which is still an unsolved question. Further, some NP-complete problems actually have algorithms running in superpolynomial, but subexponential time such as O(2模板:Sqrtn). For example, the independent set and dominating set problems for planar graphs are NP-complete, but can be solved in subexponential time using the planar separator theorem.[12]
  • "Each instance of an NP-complete problem is difficult." Often some instances, or even most instances, may be easy to solve within polynomial time. However, unless P=NP, any polynomial-time algorithm must asymptotically be wrong on more than polynomially many of the exponentially many inputs of a certain size.[13]
  • "If P=NP, all cryptographic ciphers can be broken." A polynomial-time problem can be very difficult to solve in practice if the polynomial's degree or constants are large enough. For example, ciphers with a fixed key length, such as Advanced Encryption Standard, can all be broken in constant time by trying every key (and are thus already known to be in P), though with current technology that time may exceed the age of the universe. In addition, information-theoretic security provides cryptographic methods that cannot be broken even with unlimited computing power.

The following misconceptions are frequent.

  • "NP-complete problems are the most difficult known problems." Since NP-complete problems are in NP, their running time is at most exponential. However, some problems have been proven to require more time, for example Presburger arithmetic. Of some problems, it has even been proven that they can never be solved at all, for example the Halting problem.
  • "NP-complete problems are difficult because there are so many different solutions." On the one hand, there are many problems that have a solution space just as large, but can be solved in polynomial time (for example minimum spanning tree). On the other hand, there are NP-problems with at most one solution that are NP-hard under randomized polynomial-time reduction (see Valiant–Vazirani theorem).
  • "Solving NP-complete problems requires exponential time." First, this would imply P ≠ NP, which is still an unsolved question. Further, some NP-complete problems actually have algorithms running in superpolynomial, but subexponential time such as O(2n). For example, the independent set and dominating set problems for planar graphs are NP-complete, but can be solved in subexponential time using the planar separator theorem.; ; ; .
  • "Each instance of an NP-complete problem is difficult." Often some instances, or even most instances, may be easy to solve within polynomial time. However, unless P=NP, any polynomial-time algorithm must asymptotically be wrong on more than polynomially many of the exponentially many inputs of a certain size.
  • "If P=NP, all cryptographic ciphers can be broken." A polynomial-time problem can be very difficult to solve in practice if the polynomial's degree or constants are large enough. For example, ciphers with a fixed key length, such as Advanced Encryption Standard, can all be broken in constant time by trying every key (and are thus already known to be in P), though with current technology that time may exceed the age of the universe. In addition, information-theoretic security provides cryptographic methods that cannot be broken even with unlimited computing power.

= = 常见错误观念列表 = = 常见的错误观念有:。

  • “ np 完全问题是已知的最难的问题。”由于 NP 完全问题是 NP 完全问题,其运行时间最接近于指数形式。然而,一些问题已经被证明需要更多的时间,例如 Presburger 算法。在一些问题中,甚至已经证明它们根本不可能被解决,例如停机问题。
  • “ np- 完全问题是困难的,因为有许多不同的解决方案。”一方面,有许多问题的解空间同样大,但是可以在多项式时间内解决(例如最小生成树)。另一方面,存在最多只有一个解的 np 问题在随机多项式时间图灵归约下是 np 难的(见 Valiant-Vazirani 定理)。
  • “解决 np 完全问题需要 EXPTIME。”首先,这意味着 p ≠ NP,这仍然是一个未解决的问题。此外,一些 np 完全问题实际上有算法运行在超多项式,但子指数时间,如 o (2n)。例如,平面图的独立集和控制集问题是 np 完全问题,但是可以用平面分隔定理在次指数时间内求解。; ; ; .
  • “ np 完全问题的每个实例都是困难的。”通常有些情况,甚至大多数情况,可能很容易在多项式时间内求解。然而,除非 p = NP,否则任何多项式时间算法必须在多个多项式上渐近地错误,特定大小的指数多个输入。
  • “如果 p = NP,所有密码密码都可以被破解。”如果多项式的次数或常数足够大,多项式时间问题在实际中可能很难解决。例如,具有固定密钥长度的密码,如高级加密标准密码,都可以通过尝试每一个密钥在固定时间内破解(因此已经知道是 p) ,尽管按照目前的技术,时间可能会超过宇宙的年龄。此外,资讯理论安全性还提供了无限计算能力也无法破解的加密方法。

Properties

Viewing a decision problem as a formal language in some fixed encoding, the set NPC of all NP-complete problems is not closed under:

Viewing a decision problem as a formal language in some fixed encoding, the set NPC of all NP-complete problems is not closed under:

  • union
  • intersection
  • concatenation
  • Kleene star

= = = = = = 将一个决策问题看作某种固定编码中的一种形式语言,所有 np 完全问题的集合 NPC 在:

  • 连接
  • Kleene 星下不闭合

It is not known whether NPC is closed under complementation, since NPC=co-NPC if and only if NP=co-NP, and whether NP=co-NP is an open question.[14]

It is not known whether NPC is closed under complementation, since NPC=co-NPC if and only if NP=co-NP, and whether NP=co-NP is an open question.

当且仅当 NP = co-NP,NP = co-NP 是否是一个开放性问题,NPC 是否在互补情况下闭合尚不清楚。

See also

  • Almost complete
  • Gadget (computer science)
  • Ladner's theorem
  • List of NP-complete problems
  • NP-hard
  • P = NP problem
  • Strongly NP-complete
  • Travelling Salesman (2012 film)

= = = = = = = 几乎完成小工具(计算机科学)

  • 拉德纳定理
  • NP 完全问题列表
  • NP 难
  • p = NP 问题
  • 强 NP 完全
  • 货郎担(2012年电影)

References

Citations

  1. For example, simply assigning true to each variable renders the 18th conjunct [math]\displaystyle{ \overline{m} \lor \overline{r} \lor \overline{s} }[/math] (and hence the complete formula) false.
  2. Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland. 
  3. J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. p. 84. ISBN 978-0-262-72014-4. 
  4. J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. p. 80. ISBN 978-0-262-72014-4. 
  5. Garey, Michael R.; Johnson, D. S. (1979). Victor Klee. ed. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co.. pp. x+338. ISBN 978-0-7167-1045-5. MR 519066. 
  6. Agrawal, M.; Allender, E.; Rudich, Steven (1998). "Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem". Journal of Computer and System Sciences. 57 (2): 127–143. doi:10.1006/jcss.1998.1583. ISSN 1090-2724.
  7. Agrawal, M.; Allender, E.; Impagliazzo, R.; Pitassi, T.; Rudich, Steven (2001). "Reducing the complexity of reductions". Computational Complexity. 10 (2): 117–138. doi:10.1007/s00037-001-8191-1. ISSN 1016-3328.
  8. Don Knuth, Tracy Larrabee, and Paul M. Roberts, Mathematical Writing -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-存檔,存档日期2010-08-27. § 25, MAA Notes No. 14, MAA, 1989 (also Stanford Technical Report, 1987).
  9. Knuth, D. F. (1974). "A terminological proposal". SIGACT News. 6 (1): 12–18. doi:10.1145/1811129.1811130.
  10. See the poll, or [1] -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-存檔,存档日期2011-06-07..
  11. Ball, Philip. "DNA computer helps travelling salesman". doi:10.1038/news000113-10.
  12. 脚本错误:没有“Footnotes”这个模块。; 脚本错误:没有“Footnotes”这个模块。; 脚本错误:没有“Footnotes”这个模块。; 脚本错误:没有“Footnotes”这个模块。.
  13. Hemaspaandra, L. A.; Williams, R. (2012). "SIGACT News Complexity Theory Column 76". ACM SIGACT News. 43 (4): 70. doi:10.1145/2421119.2421135.
  14. Talbot, John; Welsh, D. J. A. (2006), Complexity and Cryptography: An Introduction, Cambridge University Press, p. 57, ISBN 9780521617710, The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.

Sources


  • This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
  • Computational Complexity of Games and Puzzles
  • Tetris is Hard, Even to Approximate
  • Minesweeper is NP-complete!
  • .
  • .
  • .
  • .


这是一本经典的书,发展了这个理论,然后编目了许多 np 完全问题。

  • 游戏和拼图的计算复杂性
  • 俄罗斯方块很难,即使接近
  • 扫雷艇也是 np 完成!
  • .
  • .
  • .
  • .

Further reading


  • Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.
  • Lance Fortnow, The status of the P versus NP problem, Commun. ACM, Vol. 52, No. 9. (2009), pp. 78–86.


= 进一步阅读 = =

  • Scott Aaronson,NP-complete Problems and Physical Reality,ACM SIGACT News,Vol。36,No.1.(2005年3月) ,页。30–52.
  • Lance Fortnow,The status of The P/NP问题,Commun。美国计算机协会,卷。52,No.9.(2009) ,pp.78–86.

模板:ComplexityClasses


Category:1971 in computing

Category:Complexity classes Category:Mathematical optimization

类别: 1971年计算类别: 复杂性类别: 最优化


This page was moved from wikipedia:en:NP-completeness. Its edit history can be viewed at NP完全/edithistory