# NP完全

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, 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.

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.

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.

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.

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.

## 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.

## Formal definition

A decision problem $\displaystyle{ C }$ is NP-complete if:

1. $\displaystyle{ C }$ is in NP, and
2. Every problem in NP is reducible to $\displaystyle{ C }$ in polynomial time.

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.

$\displaystyle{ C }$ can be shown to be in NP by demonstrating that a candidate solution to $\displaystyle{ C }$ 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.

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

Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 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 $\displaystyle{ C }$, 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.

## Background

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.

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.

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

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.

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

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

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.

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 $\displaystyle{ k\gt 0 }$ 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 $\displaystyle{ 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.

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.

## 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 $\displaystyle{ X }$ is polynomial-time Turing-reducible to a problem $\displaystyle{ Y }$ if, given a subroutine that solves $\displaystyle{ Y }$ in polynomial time, one could write a program that calls this subroutine and solves $\displaystyle{ 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.

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.

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.

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 $\displaystyle{ AC_0 }$ reductions and $\displaystyle{ 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.

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.

## 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. 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 "模板:Sic exponential time" or "previously exponential time".

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.

• "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.
• "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.

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.

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.

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

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

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