更改

==Context==

==Context==

The relation between the [[complexity class]]es P and NP is studied in [[computational complexity theory]], the part of the [[theory of computation]] dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).

== The relation between the [https://wiki.swarma.org/index.php/Complexity_class complexity class]es P and NP is studied in [https://wiki.swarma.org/index.php/Computational_complexity_theory computational complexity theory], the part of the [https://wiki.swarma.org/index.php/Theory_of_computation theory of computation] dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem). The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem). = = 提出背景 = = 探讨P/NP类问题是被放在计算复杂性理论大背景中进行的，尤其是有关计算过程资源消耗的问题。这类资源消耗问题主要讨论计算时间（解决问题需要多少步骤）和计算空间（解决问题需要多少内存）。  In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is ''[https://wiki.swarma.org/index.php/Deterministic_computation deterministic]'' (given the computer's present state and any inputs, there is only one possible action that the computer might take) and ''sequential'' (it performs actions one after the other). In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic (given the computer's present state and any inputs, there is only one possible action that the computer might take) and sequential (it performs actions one after the other). 在这类问题的分析中，我们需要设计一个计算时间利用的模型。一般来说，这类模型建立在计算机确定态的和顺序态基础之上，也就是说，给定计算机的当前状态和任何输入，计算机只可能执行一种行为，并且只能按顺序地执行任务。  In this theory, the class P consists of all those ''[https://wiki.swarma.org/index.php/Decision_problem decision problem]s'' (defined [https://wiki.swarma.org/index.php/P/NP%E9%97%AE%E9%A2%98#Formal_definitions below]) that can be solved on a deterministic sequential machine in an amount of time that is [https://wiki.swarma.org/index.php/Polynomial polynomial] in the size of the input; the class [https://wiki.swarma.org/index.php/NP_(complexity) NP] consists of all those decision problems whose positive solutions can be verified in [https://wiki.swarma.org/index.php/Polynomial_time polynomial time] given the right information, or equivalently, whose solution can be found in polynomial time on a [https://wiki.swarma.org/index.php/Non-deterministic_Turing_machine non-deterministic] machine.<ref>Sipser, Michael: ''Introduction to the Theory of Computation, Second Edition, International Edition'', page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.</ref> Clearly, P ⊆ NP. Arguably, the biggest open question in [https://wiki.swarma.org/index.php/Theoretical_computer_science theoretical computer science] concerns the relationship between those two classes:

 

:Is P equal to NP? In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20. Clearly, P ⊆ NP. Arguably, the biggest open question in theoretical computer science concerns the relationship between those two classes:

The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).

:Is P equal to NP? P类问题指一类由'''%确定的按顺序的%'''的计算机完成并能在多项式时间内解决的问题；NP问题指一类可以在多项式时间内验证答案的问题，或者通过'''%非确定性的%'''计算机上可以在多项式时间内找到答案的问题。'''（来源：迈克尔 · 西普塞尔: 美国计算理论学会简介，第二版，国际版，第270页。汤姆森课程科技，2006。定义7.19和定理7.20。）'''可见，P ⊆ NP。所以说，理论计算科学中最大的开放性问题就是这两个问题类之间的关系: P类问题等价于NP类问题吗？  Since 2002, [https://wiki.swarma.org/index.php/William_Gasarch William Gasarch] has conducted three polls of researchers concerning this and related questions.<ref name="poll">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The P=?NP poll.|journal=[[SIGACT News]]|volume=33|issue=2|pages=34–47|date=June 2002| url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/564585.564599| citeseerx=10.1.1.172.1005 | s2cid=36828694 }}</ref><ref name="poll2">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The Second P=?NP poll|journal=SIGACT News|volume=74|url=http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf}}</ref><ref name="poll3">{{Cite web|url=https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf|title=Guest Column: The Third P =? NP Poll1|access-date=25 May 2020}}</ref>Confidence that P&nbsp;≠&nbsp;NP has been increasing – in 2019, 88% believed P&nbsp;≠&nbsp;NP, as opposed to 83% in 2012 and 61% in 2002. When restricted to experts, the 2019 answers became 99% believe P&nbsp;≠&nbsp;NP.<ref name="poll3" /> These polls do not imply anything about whether P=NP is true, as stated by Gasarch himself: ″This does not bring us any closer to solving P=?NP or to knowing when it will be solved, but it attempts to be an objective report on the subjective opinion of this era.″ Since 2002, William Gasarch has conducted three polls of researchers concerning this and related questions. Confidence that P ≠ NP has been increasing – in 2019, 88% believed P ≠ NP, as opposed to 83% in 2012 and 61% in 2002. When restricted to experts, the 2019 answers became 99% believe P ≠ NP. These polls do not imply anything about whether P=NP is true, as stated by Gasarch himself: ″This does not bring us any closer to solving P=?NP or to knowing when it will be solved, but it attempts to be an objective report on the subjective opinion of this era.″ 2002年以来，威廉·加萨奇就这一问题对研究人员进行了三次调查。相信P类不等于NP类的人数一直在增加——2019年，88%的人相信P类不等于NP类，而2012年和2002年的这一比例分别为83% 和61%。如果只关注专家的态度，2019年的结果显示99%的人相信P类不等于NP类。这些调查并非代表P = NP，如加萨奇说：“这个调查的目的不是为了更接近真相，而是为了更客观的了解学者们对一个未知真相的主观意见。” ==

 

= = 上下文 = = 复杂类 p 和 NP 之间的关系在计算复杂性理论中进行了研究，这部分计算理论处理在计算过程中解决给定问题所需的资源。最常见的资源是时间(解决问题需要多少步骤)和空间(解决问题需要多少内存)。

 

In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is ''[[Deterministic computation|deterministic]]'' (given the computer's present state and any inputs, there is only one possible action that the computer might take) and ''sequential'' (it performs actions one after the other).

 

In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic (given the computer's present state and any inputs, there is only one possible action that the computer might take) and sequential (it performs actions one after the other).

 

 

In this theory, the class P consists of all those ''[[decision problem]]s'' (defined [[#Formal definitions|below]]) that can be solved on a deterministic sequential machine in an amount of time that is [[polynomial]] in the size of the input; the class [[NP (complexity)|NP]] consists of all those decision problems whose positive solutions can be verified in [[polynomial time]] given the right information, or equivalently, whose solution can be found in polynomial time on a [[Non-deterministic Turing machine|non-deterministic]] machine.<ref>Sipser, Michael: ''Introduction to the Theory of Computation, Second Edition, International Edition'', page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.</ref> Clearly, P ⊆ NP. Arguably, the biggest open question in [[theoretical computer science]] concerns the relationship between those two classes:

:Is P equal to NP?

 

In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine.Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20. Clearly, P ⊆ NP. Arguably, the biggest open question in theoretical computer science concerns the relationship between those two classes:

:Is P equal to NP?

 

在这个理论中，类 p 包括所有那些决策问题(定义如下) ，这些决策问题可以在一个确定的时间序列机器上解决在一个时间量是多项式的大小的输入; 类 NP 包括所有那些决策问题，其正解可以在多项式时间验证给定正确的信息，或等价，其解可以在多项式时间在一个非确定的机器上找到。迈克尔 · 西普塞尔: 美国计算理论学会简介，第二版，国际版，第270页。汤姆森课程科技，2006。定义7.19和定理7.20。很明显，p something NP。可以说，理论计算机科学中最大的开放性问题涉及到这两个类之间的关系: p 等于 NP 吗？

 

Since 2002, [[William Gasarch]] has conducted three polls of researchers concerning this and related questions.<ref name="poll">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The P=?NP poll.|journal=[[SIGACT News]]|volume=33|issue=2|pages=34–47|date=June 2002| url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/564585.564599| citeseerx=10.1.1.172.1005 | s2cid=36828694 }}</ref><ref name="poll2">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The Second P=?NP poll|journal=SIGACT News|volume=74|url=http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf}}</ref><ref name="poll3">{{Cite web|url=https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf|title=Guest Column: The Third P =? NP Poll1|access-date=25 May 2020}}</ref> Confidence that P&nbsp;≠&nbsp;NP has been increasing – in 2019, 88% believed P&nbsp;≠&nbsp;NP, as opposed to 83% in 2012 and 61% in 2002. When restricted to experts, the 2019 answers became 99% believe P&nbsp;≠&nbsp;NP.<ref name="poll3" /> These polls do not imply anything about whether P=NP is true, as stated by Gasarch himself: ″This does not bring us any closer to solving P=?NP or to knowing when it will be solved, but it attempts to be an objective report on the subjective opinion of this era.″

 

Since 2002, William Gasarch has conducted three polls of researchers concerning this and related questions. Confidence that P ≠ NP has been increasing – in 2019, 88% believed P ≠ NP, as opposed to 83% in 2012 and 61% in 2002. When restricted to experts, the 2019 answers became 99% believe P ≠ NP. These polls do not imply anything about whether P=NP is true, as stated by Gasarch himself: ″This does not bring us any closer to solving P=?NP or to knowing when it will be solved, but it attempts to be an objective report on the subjective opinion of this era.″

 

自2002年以来，威廉 · 加萨奇就这一问题和相关问题对研究人员进行了三次民意调查。相信 p 不等于 NP 的人数一直在增加——2019年，88% 的人相信 p 不等于 NP，而2012年和2002年的这一比例分别为83% 和61% 。如果仅限于专家，2019年的答案变成了99% 的人相信 p 不等于 NP。这些民意调查并不暗示 p = NP 是否正确，正如 Gasarch 自己所说: ‘这并没有让我们更接近解决 p = ？本文试图对这个时代的主观意识作一个客观的报道。’′

 

==NP-completeness==

==NP-completeness==

[[File:P np np-complete np-hard.svg|thumb|300px|right|[[Euler diagram]] for [[P (complexity)|P]], [[NP (complexity)|NP]], NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)|链接=Special:FilePath/P_np_np-complete_np-hard.svg]]

==[[File:P np np-complete np-hard.svg|thumb|300px|right|[https://wiki.swarma.org/index.php/Euler_diagram Euler diagram] for [https://wiki.swarma.org/index.php/P_(complexity) P], [https://wiki.swarma.org/index.php/NP_(complexity) NP], NP-complete, and NP-hard set of problems (excluding the empty language and its complement, which belong to P but are not NP-complete)|链接=Special:FilePath/P_np_np-complete_np-hard.svg]]{{Main article|NP-completeness}} To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.   To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP. 为了解决P/NP问题，了解NP完全性的概念是非常有帮助的。NP完全问题指一类可以将NP问题简化为多项式时间内可解的问题，而且这类问题的解也可以在多项式时间内验证。理论上讲，任何NP问题都可以转化为NP完全问题。换一种方式来说，一个NP完全问题至少跟其他NP问题一样“困难”。  [https://wiki.swarma.org/index.php/NP-hard NP-hard] problems are those at least as hard as NP problems; i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP; i.e., they need not have solutions verifiable in polynomial time. NP-hard problems are those at least as hard as NP problems; i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP; i.e., they need not have solutions verifiable in polynomial time. NP困难问题是指至少和NP问题一样困难的问题，也就是说，所有NP问题都可以（在多项式时间内）简化为NP困难问题。NP困难问题不一定是NP问题，它们不需要在多项式时间内有可验证的解。  For instance, the [https://wiki.swarma.org/index.php/Boolean_satisfiability_problem Boolean satisfiability problem] is NP-complete by the [https://wiki.swarma.org/index.php/Cook%E2%80%93Levin_theorem Cook–Levin theorem], so ''any'' instance of ''any''problem in NP can be transformed mechanically into an instance of the Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many such NP-complete problems. If any NP-complete problem is in P, then it would follow that P = NP. However, many important problems have been shown to be NP-complete, and no fast algorithm for any of them is known. For instance, the Boolean satisfiability problem is NP-complete by the Cook–Levin theorem, so any instance of any problem in NP can be transformed mechanically into an instance of the Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many such NP-complete problems. If any NP-complete problem is in P, then it would follow that P = NP. However, many important problems have been shown to be NP-complete, and no fast algorithm for any of them is known. 例如，根据 Cook-Levin 定理，'''%布尔可满足性问题%是'''NP完全问题，因此任何 NP 问题的实例都可以在多项式时间内被转化为'''%布尔可满足性问题%'''的实例。它是许多NP完全问题中的一个。如果任意一个NP完全问题在P类问题中，那么P = NP。然而，许多重要的问题已经被证明是NP完全的，并且至今没有一个更快速的算法。  Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a [https://wiki.swarma.org/index.php/Turing_machine Turing machine] ''M'' guaranteed to halt in polynomial time, does there exist a polynomial-size input that ''M'' will accept?<ref name="Scott">{{Cite web|author=Scott Aaronson|title=PHYS771 Lecture 6: P, NP, and Friends|url=http://www.scottaaronson.com/democritus/lec6.html |access-date=27 August 2007}}</ref> It is in NP because (given an input) it is simple to check whether ''M'' accepts the input by simulating ''M''; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine ''M'' that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists. Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a Turing machine M guaranteed to halt in polynomial time, does there exist a polynomial-size input that M will accept? It is in NP because (given an input) it is simple to check whether M accepts the input by simulating M; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine M that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists. 其实根据这个定义，NP完全问题不那么容易找到，但是我们可以人为设计一个NP完全问题。例如：假设一个在多项式时间停止的图灵机M，是否存在一个图灵机M可以计算的多项式大小的输入值？这个问题就是NP的，因为给定一个输入值，我们很容易通过模拟M来检查M是否接受输入值；同时，它也是NP完全的，因为任何NP问题的特定实例的验证器都可以被转换为一个多项式时间机器M，然后放入输入值进行验证。最后判断实例是否存在的这个问题就变成了判断是否有一个有效的输入值。（翻译到此） ==

{{Main article|NP-completeness}}

To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.

 

 

 

To attack the P = NP question, the concept of NP-completeness is very useful. NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.

 

为了解决 p = NP 问题，NP- 完全性的概念是非常有用的。Np- 完全问题是一组问题，其中任何一个 np- 问题都可以在多项式时间内约化，其解仍可在多项式时间内验证。也就是说，任何 NP 问题都可以转化为 NP 完全问题。非正式地，NP- 完全问题是一个 NP 问题，至少与 NP 中的任何其他问题一样“困难”。

 

[[NP-hard]] problems are those at least as hard as NP problems; i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP; i.e., they need not have solutions verifiable in polynomial time.

 

NP-hard problems are those at least as hard as NP problems; i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP; i.e., they need not have solutions verifiable in polynomial time.

 

 

For instance, the [[Boolean satisfiability problem]] is NP-complete by the [[Cook–Levin theorem]], so ''any'' instance of ''any'' problem in NP can be transformed mechanically into an instance of the Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many such NP-complete problems. If any NP-complete problem is in P, then it would follow that P = NP. However, many important problems have been shown to be NP-complete, and no fast algorithm for any of them is known.

 

For instance, the Boolean satisfiability problem is NP-complete by the Cook–Levin theorem, so any instance of any problem in NP can be transformed mechanically into an instance of the Boolean satisfiability problem in polynomial time. The Boolean satisfiability problem is one of many such NP-complete problems. If any NP-complete problem is in P, then it would follow that P = NP. However, many important problems have been shown to be NP-complete, and no fast algorithm for any of them is known.

 

例如，根据 Cook-Levin 定理，布尔可满足性问题是 NP 完全的，因此任何 NP 问题的实例都可以在多项式时间内被机械地转化为布尔可满足性问题的实例。布尔可满足性问题是许多 np 完全问题中的一个。如果任意一个 NP 完全问题在 p 中，那么它将遵循 p = NP。然而，许多重要的问题已经被证明是 np 完全的，并且没有一个快速的算法是已知的。

 

Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a [[Turing machine]] ''M'' guaranteed to halt in polynomial time, does there exist a polynomial-size input that ''M'' will accept?<ref name="Scott">{{Cite web|author=Scott Aaronson|title=PHYS771 Lecture 6: P, NP, and Friends|url=http://www.scottaaronson.com/democritus/lec6.html |access-date=27 August 2007}}</ref> It is in NP because (given an input) it is simple to check whether ''M'' accepts the input by simulating ''M''; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine ''M'' that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.

 

Based on the definition alone it is not obvious that NP-complete problems exist; however, a trivial and contrived NP-complete problem can be formulated as follows: given a description of a Turing machine M guaranteed to halt in polynomial time, does there exist a polynomial-size input that M will accept? It is in NP because (given an input) it is simple to check whether M accepts the input by simulating M; it is NP-complete because the verifier for any particular instance of a problem in NP can be encoded as a polynomial-time machine M that takes the solution to be verified as input. Then the question of whether the instance is a yes or no instance is determined by whether a valid input exists.

 

The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete [[Latin square]]s in polynomial time.<ref>{{Cite web|url=http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html|title=MSc course: Foundations of Computer Science|website=www.cs.ox.ac.uk|access-date=25 May 2020}}</ref> This in turn gives a solution to the problem of partitioning [[multipartite graph|tri-partite graphs]] into triangles,<ref>{{cite journal |author=Colbourn, Charles J. |title=The complexity of completing partial Latin squares |journal=Discrete Applied Mathematics |volume=8 |issue=1 |year=1984 |pages=25–30 |doi=10.1016/0166-218X(84)90075-1 |doi-access=free }}</ref> which could then be used to find solutions for the special case of SAT known as 3-SAT,<ref>{{cite journal |author=I. Holyer |title=The NP-completeness of some edge-partition problems |journal=SIAM J. Comput. |volume=10 |year=1981 |issue=4 |pages=713&ndash;717|doi=10.1137/0210054 }}</ref> which then provides a solution for general Boolean satisfiability.  So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time.  Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".

The first natural problem proven to be NP-complete was the Boolean satisfiability problem, also known as SAT. As noted above, this is the Cook–Levin theorem; its proof that satisfiability is NP-complete contains technical details about Turing machines as they relate to the definition of NP. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] provided a simpler way to show that many other problems are also NP-complete, including the game Sudoku discussed earlier. In this case, the proof shows that a solution of Sudoku in polynomial time could also be used to complete [[Latin square]]s in polynomial time.<ref>{{Cite web|url=http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html|title=MSc course: Foundations of Computer Science|website=www.cs.ox.ac.uk|access-date=25 May 2020}}</ref> This in turn gives a solution to the problem of partitioning [[multipartite graph|tri-partite graphs]] into triangles,<ref>{{cite journal |author=Colbourn, Charles J. |title=The complexity of completing partial Latin squares |journal=Discrete Applied Mathematics |volume=8 |issue=1 |year=1984 |pages=25–30 |doi=10.1016/0166-218X(84)90075-1 |doi-access=free }}</ref> which could then be used to find solutions for the special case of SAT known as 3-SAT,<ref>{{cite journal |author=I. Holyer |title=The NP-completeness of some edge-partition problems |journal=SIAM J. Comput. |volume=10 |year=1981 |issue=4 |pages=713&ndash;717|doi=10.1137/0210054 }}</ref> which then provides a solution for general Boolean satisfiability.  So a polynomial time solution to Sudoku leads, by a series of mechanical transformations, to a polynomial time solution of satisfiability, which in turn can be used to solve any other NP-problem in polynomial time.  Using transformations like this, a vast class of seemingly unrelated problems are all reducible to one another, and are in a sense "the same problem".

==Reasons to believe P ≠ NP or P = NP==

==Reasons to believe P ≠ NP or P = NP==

Cook provides a restatement of the problem in <small>THE P VERSUS NP PROBLEM</small> as: ''Does'' P = NP ''?''.<ref name="Official Problem Description"/> According to polls,<ref name="poll"/><ref>{{cite journal|title=P vs. NP poll results|journal=Communications of the ACM|date=May 2012|volume=55|issue=5|page=10|first=Jack|last=Rosenberger|url=http://mags.acm.org/communications/201205?pg=12}}</ref> most computer scientists believe that P&nbsp;≠&nbsp;NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see [[List of NP-complete problems]]). These algorithms were sought long before the concept of NP-completeness was even defined ([[Karp's 21 NP-complete problems]], among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = [[co-NP]] and P = [[PH (complexity)|PH]].

Cook provides a restatement of the problem in <small>THE P VERSUS NP PROBLEM</small> as: ''Does'' P = NP ''?''.<ref name="Official Problem Description"/> According to polls,<ref name="poll">{{Cite journal|author=William I. Gasarch| author1-link=William Gasarch | title=The P=?NP poll.|journal=[[SIGACT News]]|volume=33|issue=2|pages=34–47|date=June 2002| url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf|doi=10.1145/564585.564599| citeseerx=10.1.1.172.1005 | s2cid=36828694 }}</ref><ref>{{cite journal|title=P vs. NP poll results|journal=Communications of the ACM|date=May 2012|volume=55|issue=5|page=10|first=Jack|last=Rosenberger|url=http://mags.acm.org/communications/201205?pg=12}}</ref> most computer scientists believe that P&nbsp;≠&nbsp;NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see [[List of NP-complete problems]]). These algorithms were sought long before the concept of NP-completeness was even defined ([[Karp's 21 NP-complete problems]], among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = [[co-NP]] and P = [[PH (complexity)|PH]].

Cook provides a restatement of the problem in THE P VERSUS NP PROBLEM as: Does P = NP ?. According to polls, most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see List of NP-complete problems). These algorithms were sought long before the concept of NP-completeness was even defined (Karp's 21 NP-complete problems, among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = co-NP and P = PH.

Cook provides a restatement of the problem in THE P VERSUS NP PROBLEM as: Does P = NP ?. According to polls, most computer scientists believe that P ≠ NP. A key reason for this belief is that after decades of studying these problems no one has been able to find a polynomial-time algorithm for any of more than 3000 important known NP-complete problems (see List of NP-complete problems). These algorithms were sought long before the concept of NP-completeness was even defined (Karp's 21 NP-complete problems, among the first found, were all well-known existing problems at the time they were shown to be NP-complete). Furthermore, the result P = NP would imply many other startling results that are currently believed to be false, such as NP = co-NP and P = PH.