P完全性（P-completeness），理学-计算机科学技术-计算机科学理论-计算复杂性-归约，P完全性（P-completeness）刻画了多项式时间P类中在对数空间归约（见对数空间L类）下最难的一类问题。有穷字母表上所有穷字符串构成集合的一个子集A称为一个语言，它对应一个判定问题：对于任意的，判定是否在L中？一个判定问题用一个语言描述。P是确定型图灵机在多项式时间可判定的问题（语言）类（见多项式时间P类）。如下问题都是P问题：①2-SAT问题：判定一个2-CNF公式是否可满足；②欧拉（Euler）图问题：判定一个无向图是否是欧拉图；③平面图问题：判定一个无向图是否是平面图；④PATH问题：给定一个图G和结点对s和t，判定从s到t是否有路径可达。等等。与NP完全性类似，借助对数空间归约引入P完全性。值得注意的是NP完全性中多项式归约不再适用于P完全性的引入，原因是多项式归约在P类问题无法区分两个P问题的复杂度量级。对于两个A和B，问题A在对数空间归约到问题B（简称L-归约，记为）是指存在一个对数空间可计算的转换函数，使得：对于任意的，（见对数空间L类）。