更改

:<math>\mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ 整数} p, q > 1 \right \}</math>

:<math>\mathrm{COMPOSITE} = \left \{x\in\mathbb{N} \mid x=pq \text{ 整数} p, q > 1 \right \}</math>

:<math>R = \left \{(x,y)\in\mathbb{N} \times\mathbb{N} \mid 1<y \leq \sqrt x \text{ and } y \text{ 整除} x \right \}.</math>

:<math>R = \left \{(x,y)\in\mathbb{N} \times\mathbb{N} \mid 1<y \leq \sqrt x \text{ 并且} y \text{ 整除} x \right \}.</math>

显然，x是否为合数这个问题等价于x是否在集合COMPOSITE中。通过验证其满足以上定义可以说明 COMPOSITE ∈ NP（如果我们用二进制表示自然数）【对于维基百科中括号里这句话的目的，并没有搞清楚】。

显然，x是否为合数这个问题等价于x是否在集合COMPOSITE中。通过验证其满足以上定义可以说明 COMPOSITE ∈ NP（如果我们用二进制表示自然数）【对于维基百科中括号里这句话的目的，并没有搞清楚】。

COMPOSITE恰巧也在P中，这个事实在AKS primality test中提到过。

COMPOSITE恰巧也在P中，这个事实在AKS primality test中提到过。<ref name="Agrawal" />

===NP完全===

===NP完全===