I assume that you are looking for intuitive definitions, since the technical definitions require quite some time to understand.
(我假设您正在寻找直观的定义，因为技术定义需要花费很多时间才能理解。)
First of all, let's remember a preliminary needed concept to understand those definitions. (首先，让我们记住一个初步的概念，以理解这些定义。)
- Decision problem : A problem with a yes or no answer.
(决策问题 ： 是或否的问题。)
Now, let us define those complexity classes .
(现在，让我们定义那些复杂度类 。)
P (P)
P is a complexity class that represents the set of all decision problems that can be solved in polynomial time .
(P是一个复杂度类，表示可以在多项式时间内解决的所有决策问题的集合 。)
That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.
(即，给定问题的实例，可以在多项式时间内确定答案是或否。)
Example
(例)
Given a connected graph G , can its vertices be coloured using two colours so that no edge is monochromatic?
(给定一个连通图G ，其顶点可以使用两种颜色进行着色，以确保没有边是单色的吗？)
Algorithm: start with an arbitrary vertex, color it red and all of its neighbours blue and continue.
(算法：从任意顶点开始，将其着色为红色，并将其所有邻居着色为蓝色，然后继续。)
Stop when you run out of vertices or you are forced to make an edge have both of its endpoints be the same color. (当顶点用尽时，或者在使边缘的两个端点都具有相同颜色的情况下，请停止。)
NP (NP)
NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time.
(NP是一个复杂性类，代表所有决策问题的集合，对于这些问题，答案为“是”的实例具有可以在多项式时间内验证的证明。)
This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) to the answer being yes, we can check that it is correct in polynomial time.
(这意味着，如果有人给我们一个问题的实例，并且答案为是的证明（有时称为见证人），我们可以检查它在多项式时间内是否正确。)
Example
(例)
Integer factorisation is in NP.
(整数分解在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和m ，是否有一个整数f与1 < f < m使得f划分n （ f是小因子n ）？)
This is a decision problem because the answers are yes or no.
(这是一个决策问题，因为答案是是或否。)
If someone hands us an instance of the problem (so they hand us integers n and m ) and an integer f with 1 < f < m , and claim that f is a factor of n (the certificate), we can check the answer in polynomial time by performing the division n / f . (如果有人将问题的一个实例交给我们（因此他们将整数n和m交给我们）和1 < f < m的整数f并声称f是n的因子（证书），我们可以在通过执行除法n / f 多项式时间 。)
NP-Complete (NP完成)
NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.
(NP-Complete是一个复杂度类别，表示NP中所有问题X的集合，对于该问题，可以在多项式时间内将任何其他NP问题Y简化为X)
Intuitively this means that we can solve Y quickly if we know how to solve X quickly.
(直观地讲，这意味着如果我们知道如何快速求解X ，就可以快速求解Y)
Precisely, Y is reducible to X , if there is a polynomial time algorithm f to transform instances y of Y to instances x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes. (准确地说， Y还原为X ，如果存在一个多项式时间算法f变换实例y的Y到实例x = f(y)的X在多项式时间，与该回答该属性y是肯定的，当且仅如果f(y)的答案为是。)
Example
(例)
3-SAT .
(3-SAT 。)
This is the problem wherein we are given a conjunction (ANDs) of 3-clause disjunctions (ORs), statements of the form (这是一个问题，其中我们被赋予三子句析取（OR）的连接（AND），其形式为)
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR x_v3n)
where each x_vij is a boolean variable or the negation of a variable from a finite predefined list (x_1, x_2, ... x_n) .
(其中每个x_vij是布尔变量或有限预定义列表(x_1, x_2, ... x_n)变量的取反。)
It can be shown that every NP problem can be reduced to 3-SAT .
(可以证明， 每个NP问题都可以简化为3-SAT 。)
The proof of this is technical and requires use of the technical definition of NP ( based on non-deterministic Turing machines ). (这是技术上的证明，需要使用NP的技术定义（ 基于非确定性图灵机 ）。)
This is known as Cook's theorem . (这被称为库克定理 。)
What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time (one problem to rule them all).
(使NP完全问题重要的原因是，如果可以找到确定性的多项式时间算法来解决其中一个问题，那么每个NP问题都可以在多项式时间内解决（一个问题可以全部解决）。)
NP-hard (NP硬)
Intuitively, these are the problems that are at least as hard as the NP-complete problems .
(直观地讲，这些问题至少与NP完全问题一样困难 。)
Note that NP-hard problems do not have to be in NP , and they do not have to be decision problems . (请注意，NP难题不一定在NP中 ， 它们也不必是决策问题 。)
The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y , such that Y is reducible to X in polynomial time .
(这里的精确定义是，如果存在一个NP完全问题Y ，那么问题X就是NP难题，这样Y可以在多项式时间内还原为X)
But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time.
(但是由于可以在多项式时间内将任何NP-完全问题简化为任何其他NP-完全问题，因此可以在多项式时间内将所有NP-完全问题简化为任何NP-hard问题。)
Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time. (然后，如果在多项式时间内有一个NP-hard问题的解决方案，那么在多项式时间内有一个所有NP问题的解决方案。)
Example
(例)
The halting problem is an NP-hard problem.
(暂停问题是NP难题。)
This is the problem that given a program P and input I , will it halt? (这是给定程序P和输入I ，它会停止吗？)
This is a decision problem but it is not in NP. (这是一个决策问题，但不是NP问题。)
It is clear that any NP-complete problem can be reduced to this one. (显然，任何NP完全问题都可以简化为这一问题。)
As another example, any NP-complete problem is NP-hard. (作为另一个例子，任何NP完全问题都是NP困难的。)
My favorite NP-complete problem is the Minesweeper problem .
(我最喜欢的NP完全问题是扫雷问题 。)
P = NP (P = NP)
This one is the most famous problem in computer science, and one of the most important outstanding questions in the mathematical sciences.
(这是计算机科学中最著名的问题，也是数学科学中最重要的突出问题之一。)
In fact, the Clay Institute is offering one million dollars for a solution to the problem (Stephen Cook's writeup on the Clay website is quite good). (实际上， 克莱研究所 （ Clay Institute ）愿意出一百万美元来解决这个问题（斯蒂芬·库克（Stephen Cook）在克莱网站上的写着很好。)
It's clear that P is a subset of NP.
(显然，P是NP的子集。)
The open question is whether or not NP problems have deterministic polynomial time solutions. (尚未解决的问题是NP问题是否具有确定的多项式时间解。)
It is largely believed that they do not. (人们普遍认为他们没有。)
Here is an outstanding recent article on the latest (and the importance) of the P = NP problem: The Status of the P versus NP problem . (这是一篇有关P = NP问题的最新（及其重要性）的近期杰出文章： P与NP问题的现状 。)
The best book on the subject is Computers and Intractability by Garey and Johnson.
(最好的书是Garey和Johnson撰写的Computers and Intractability 。)
