134
个编辑
更改
跳到导航
跳到搜索
小第97行：
第97行： − + 第105行：
第105行： − 复杂性类P和NP的关系是在计算复杂性理论中被研究的，它是计算理论的分支，与计算任务所需资源相关。最常见的资源是时间（求解问题需要多少步骤）和空间（求解问题需要多少内存）。+ − 在这种分析中，需要分析时间的计算机模型。通常，此类模型假定计算机具有确定性（给定计算机的当前状态，对于任何输入，都只采取一种可能的操作）和连续性（它一个接一个地执行操作）。+ − 在这个理论中，P类问题由所有这样的决策问题（定义如下）组成，它们可以在确定有限性的机器上求解，运行时间是输入规模的多项式函数；NP类由所有这样的决策问题组成，如果有正确的信息，它们的定解可以在多项式时间内验证，或者可以说，它的解可以用非确定图灵机在多项式时间内找到。很明显，P⊆ NP。可以说，理论计算机科学中最重大的公开问题就是这两门类问题间的关系：+ − − − − 自2002年以来，威廉·加萨奇就这一问题及相关问题对研究人员进行了三次民意调查。认为P≠ NP的人数一直在增加。2019年，88%的人相信P≠ NP，而2012年和2002年分别为83%和61%。当受访仅限于专家时，2019年的结果是99%相信P≠ NP。这些调查对于P=NP是否正确说明不了问题。正如Gasarch自己所说：“这并没有让我们离解决P=？NP更进一步NP或是要知道它什么时候会被解决，但它试图成为对这个时代主观观点的客观报道。”
→背景： 二修
在这类问题的分析中，我们需要设计一个计算时间利用的模型。一般来说，这类模型建立在计算机确定态的和顺序态基础之上，也就是说，给定计算机的当前状态和任何输入，计算机只可能执行一种行为，并且只能按顺序地执行任务。
在这类问题的分析中，我们需要设计一个计算时间利用的模型。一般来说，这类模型建立在计算机确定态的和顺序态基础之上，也就是说，给定计算机的当前状态和任何输入，计算机只可能执行一种行为，并且只能按顺序地执行任务。
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:
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 name=":11">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?
:Is P equal to NP?
==背景==
==背景==
复杂性类中P和NP的关系是在计算复杂性理论中被研究的，计算复杂性理论是计算理论的分支，处理计算任务所需资源的相关问题。最常见的资源是时间（求解问题需要多少步骤）和空间（求解问题需要多少内存）。
在这种分析中，需要用于分析时间的计算机模型。通常，此类模型假定计算机具有确定性（给定计算机的当前状态，对于任何输入，只采取一种可能的操作）和连续性（它一个接一个地执行操作）。
在这个理论中，P类问题由所有这样的决策问题组成，它们可以在确定有限性的机器上求解，运行时间是输入规模的多项式函数；NP类由所有这样的决策问题组成，如果有正确的信息，它们的定解可以在多项式时间内验证，或者说，它的解可以用非确定图灵机在多项式时间内找到。<ref name=":11" />很明显，P⊆ NP。可以说，理论计算机科学中最重大的公开问题就是这两类问题间的关系：<blockquote>P是否等于NP？</blockquote>自2002年以来，威廉·加萨奇（William Gasarch）就这一问题及相关问题对研究人员进行了三次民意调查。<ref name="poll" /><ref name="poll2" /><ref name="poll3" />认为P ≠ NP的人数一直在增加。2019年，88%的人相信P ≠ NP，而2012年和2002年分别为83%和61%。当受访者仅限于专家时，2019年这个比例是99%。<ref name="poll3" />这些调查结果无法说明P = NP正确与否。正如加萨其（Gasarch）自己所说：“这并没有让我们离解决P =？NP更进一步或是知道它什么时候会被解决，但它试图成为对这个时代主观观点的客观报道。”
P是否等于NP？
==NP-completeness==
==NP-completeness==