非确定性多项式（NP）与多项式（P）？
我实际上是在寻找描述NP alogrithm的实际含义以及哪种算法/问题可以归类为NP问题
我在网上阅读了很多资源。 我喜欢
多项式问题： -如果运行时间是输入**大小的多项式函数，例如，如果算法运行在线性时间或二次或三次时间，那么我们说算法运行在多项式时间。 示例可以是二进制搜索
现在我明白了多项式问题。 但不能与NP进行对比。
NP（非确定多项式问题）： -
现在有很多程序不是（必然）在普通计算机上运行多项式时间，而是在非确定性图灵机上以多项式时间运行。 这些程序解决NP中的问题，它代表非确定性多项式时间。
我无法理解/想象在常规计算机上不能在多项式时间运行的示例。 根据我目前的理解，每个问题/算法都可以用一些可以或不可以与时间成比例的多项式函数来解决。 我知道我在这里错过了一些东西，但真的无法理解这个概念。 有人能给出在普通计算机上的多项式时间无法解决的问题的例子，但可以用多项式时间来验证吗？
在上面提到的第二个链接中给出的例子之一是Integer factorization is in NP. This is the problem that given integers n and m, is there an integer f with 1 < f < m, such that f divides n (f is a small factor of n)? Integer factorization is in NP. This is the problem that given integers n and m, is there an integer f with 1 < f < m, such that f divides n (f is a small factor of n)? 为什么在普通计算机上的某些多项式时间无法解决？ 我们可以检查从n到n的所有数字，如果他们分割n或不。 对 ？ 此外，在验证部分来到这里（我的意思是，如果它可以在多项式时间内解决，但如何在多项式时间验证问题解决方案）？
你的问题涉及几点。
首先，在与您的问题相关的意义上，问题的大小被定义为问题表示的大小。 所以，例如，当你写关于n的除数问题时。 n的表示是什么？ 它是一系列长度为q的字符（我不想比这更具体）。 一般来说，n是q的指数。 所以当你谈论从1到n的简单循环时，你所谈论的是输入大小呈指数级增长的东西。 例如，数字“999999999999999”代表数字999999999999999.这是一个相当大的数字，但在这里用12个字符表示。
其次，尽管定义类NP的方法不止一种，但对于决策问题（这是你在问题中提出的类型，即是否为真）最简单的方法是，如果答案是真的，那么有一个可以在多项式时间内验证的“证书”。 例如，考虑Hamilton路问题。 这（可能）是一个难以解决的问题，但是，如果给哈密尔顿路径作为答案，很容易验证它是如此; 具体来说，它可以在多项式时间内完成。 对于Hamilton路径问题，路径是一个多项式时间可验证的证书，因此这个问题是NP。
可能值得注意的是，“检查多项式时间解决方案”的思想与非确定性图灵机解决问题有关：在一个正常的（确定性的）图灵机中，有一套明确定义的指令集，告诉机器究竟要做什么在任何情况下都会这样做（“如果你处于状态3并看到'a'，向左移动，如果你处于状态7并看到'c'，用'b'覆盖它，等等。”）在一个非确定性的图灵机中，有多种选项可用于在某些情况下做什么（“如果您处于状态3并看到'a'，则右移或用'b'覆盖它”）。 就算法而言，这让我们可以“猜测”解决方案，因为如果我们可以将问题编码为字母表中的语言*，那么我们可以使用非确定性的图灵机在该字母表上生成字符串，然后使用标准确定性的）图灵机确保它是正确的。 如果我们假设我们总是做出正确的猜测，那么算法的运行时间就是确定性检查部分的运行时间，对于NP问题，运行时间在多项式时间内运行。 这就意味着一个问题在'非确定性图灵机上的多项式时间内可确定'，以及为什么它通常被简单表述为'在多项式时间内检查解决方案/证书'。
*示例：哈密顿路径问题可以编码如下：
标记图1到n的顶点，其中n是顶点数。 我们的字母表是数字1到n，而我们的语言包含所有这些词汇
a）从1到n的每个整数只出现一次
和
b）对于一个单词中的每个连续的整数对，连接这些标签的顶点
多项式时间： -可以在输入大小的多项式时间内解决的问题称为多项式问题。 用简单的话来说： - 这里解决问题的速度很快。 例如排序，二进制搜索
非确定性多项式： -理论上可以用多项式时间验证的问题，而不考虑实际解的时间复杂性（可以是多项式或不是多项式）。 所以P的一些问题也可以是NP。
但是非正式的人们在谈话/帖子在下面的意义上使用NP项时在输入大小的多项式时间内无法解决的问题被称为多项式问题。 用简单的话来说： - 这里解决问题的速度并不快。 您可能需要尝试不同的排列/组合或猜测工作。 但验证部分速度快，可以在多项式时间内完成。 像输入一些数字X并将数字分成两组，其总和的差异最小
我真的很喜欢亚历克斯弗林特的答案，在https://www.quora.com/What-are-P-NP-NP-complete-and-NP-hard.Above就是这个意思。
链接地址: http://www.djcxy.com/p/39989.html上一篇: Non deterministic Polynomial(NP) vs Polynomial(P)?
下一篇: How many decision variables can be solved for Mixed Integer Programming?