← 返回单词列表

p-complete

adj 编号: P00013

表示某个问题在复杂性类 P 中，并且 P 中的所有其他问题都能在多项式时间内归约到它；也可指这类问题的集合。

💡 记忆钩子

把 P 想成一组能在多项式时间内解决的问题；其中一个问题如果像“总闸门”一样，P 里的任何问题都能高效转换成它，它就是 P-complete，而所有这样的“总闸门”合起来就是 P-complete 类。

📝 学习建议

先记住它描述的是复杂性类 P 内部的“完整性”，不要望文生义地把它理解成“所有问题都很完整”或直接等同于 NP-complete。

📖 中文释义

adj

core P 类中的完全问题

📖 这个形容词表示：某问题属于 P，而且 P 中的任何其他问题都可以在多项式时间内映射或归约到它。因此，它可以看作 P 这一复杂性类中最能代表整体难度的一类问题。

💡 常用句型是“a P-complete problem”或“problem X is P-complete”。它主要出现在计算复杂性理论的正式讨论中，通常直接修饰 problem、task 等名词。不要只看到问题属于 P 就称其为 P-complete，因为还必须说明 P 中的其他问题都能在多项式时间内归约到它。

not-comparable

The researchers proved that the scheduling problem is P-complete.

研究人员证明这个调度问题是 P-complete 问题。

name

core P-complete 类

📖 这个名词指所有同时属于 P、并且能让 P 中其他问题在多项式时间内归约到它们的问题所组成的集合，也就是 P 中的完全问题类。

💡 常用句型是“a problem is in P-complete”或“P-complete includes ...”。它作为复杂性类名称时通常不加冠词，也不表示单独的一个问题。学习时先把它理解为一组问题的名称，再区分“某问题是 P-complete”和“某问题属于 P-complete”。

Several graph problems are known to be in P-complete.

已知有几个图问题属于 P-complete 类。

🏷 单词标签 & 词根