本文主要是介绍什么是P问题、 NP 问题、NPC问题 ？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
千禧难题之一：证明 P=NP？
首先需要了解时间复杂度与多项式的概念：
对于一个问题的规模，比如任意给定一个3x3魔方的状态，求解最快多少步骤可以还原？这里的3则为该问题的规模
通常将问题的规模记为n，通常算法的时间复杂度有以下几种情况：
首先单项式指由变量、系数以及它们之间的乘除、幂运算（非负整数次方）得到的表达式。
由若干个单项式相加组成的代数式叫做多项式。
首先解释一下什么是 P 问题、NP问题、NPC问题（也称NP完全问题）：
一个问题可以在多项式 (Polynominal) 时间内得到解决的问题称为 P问题；
一个问题通过分析求解也不能在多项式时间内得到正解，但是如果给定一个候选答案，我们能够在多项式时间内验证这个答案是不是该问题的解， 这类问题称为 NP问题；（显然P问题是NP问题的一个子集）
一个问题：1.能够在多项式时间内验证给定答案是不是正解，2.任何一个NP问题在多项式时间内将输入(input)转化成为一个NP完全问题（NP-Complete Problem，即规约），那么只要其中一个问题(NP问题或NP完全问题)可以在多项式时间内解决，那么另一个问题也将可以在多项式时间内解决。 这类问题则称为NPC问题
另外，若一个问题既不可以在多项式时间内求解，也不可以在多项式时间内验证给定解，那么这类问题称为Non-NP (非NP问题）
目前 P NP 是已知的，而对于进一步的猜想： P = NP 是否成立？对为什么成立或为什么不成立给出证明。
这篇关于什么是P问题、 NP 问题、NPC问题 ？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
