4
个编辑
更改
跳到导航
跳到搜索
小第67行：
第67行： − + + + + + + + + + − + + + + − ==[[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，然后放入输入值进行验证。最后判断实例是否存在的这个问题就变成了判断是否有一个有效的输入值。（翻译到此） ==+ + + + + + + + + + + + + + + +
→Context
==Context==
==Context==
== 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:
== 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:
: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 ⊆ 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 ≠ 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.<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，如加萨奇说：“这个调查的目的不是为了更接近真相，而是为了更客观的了解学者们对一个未知真相的主观意见。” ==
: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 ≠ 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.<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，如加萨奇说：“这个调查的目的不是为了更接近真相，而是为了更客观的了解学者们对一个未知真相的主观意见。” ==
==NP-completeness==
==NP-completeness==
<small></small><small>{{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.</small>
<small>为了解决P/NP问题，了解NP完全性的概念是非常有帮助的。NP完全问题指一类可以将NP问题简化为多项式时间内可解的问题，而且这类问题的解也可以在多项式时间内验证。理论上讲，任何NP问题都可以转化为NP完全问题。换一种方式来说，一个NP完全问题至少跟其他NP问题一样“困难”。</small>
<small>[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.</small>
<small>NP困难问题是指至少和NP问题一样困难的问题，也就是说，所有NP问题都可以（在多项式时间内）简化为NP困难问题。NP困难问题不一定是NP问题，它们不需要在多项式时间内有可验证的解。</small>
<small>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.</small>
<small>例如，根据 Cook-Levin 定理，'''%布尔可满足性问题%是'''NP完全问题，因此任何 NP 问题的实例都可以在多项式时间内被转化为'''%布尔可满足性问题%'''的实例。它是许多NP完全问题中的一个。如果任意一个NP完全问题在P类问题中，那么P = NP。然而，许多重要的问题已经被证明是NP完全的，并且至今没有一个更快速的算法。</small>
<small>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.</small>
<small>其实根据这个定义，NP完全问题不那么容易找到，但是我们可以人为设计一个NP完全问题。例如：假设一个在多项式时间停止的图灵机M，是否存在一个图灵机M可以计算的多项式大小的输入值？这个问题就是NP的，因为给定一个输入值，我们很容易通过模拟M来检查M是否接受输入值；同时，它也是NP完全的，因为任何NP问题的特定实例的验证器都可以被转换为一个多项式时间机器M，然后放入输入值进行验证。最后判断实例是否存在的这个问题就变成了判断是否有一个有效的输入值。（翻译到此）</small>
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–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–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".