在多项式等价关系下P类的结构

The Structure of the Class P Under the Polynomial Equivalence Relation

M. R. Carey 和认D. S. Johnson在《计算机和难解性,NP完全性理论导引》一书中说在多项式等价关系下,P类形成一个“最小的”等价类。这个论断是错误的。本文证明在多项式等价关系下,P类可划分成三个等价类:A={Σ~*∶Σ是字母表},B={φ},C=P-(AUB),并且证明在诱导出的偏序关系下,A和B是两个“极小元”。

In their book “Computers and intractability, a guide to the theory of Np-comple-teness”, M. R. Garey and D. S. Johnson said that the class P forms the“least” equivalence class under the polynomial equivalence relation. This conclusion is not correct. In this paper, we proved that under this relation the class P is partitioned into 3 equivalence classes: A= {Σ:Σ is an alphabet}, B= { } and C = P-(A∪B), and proved that A and B are two “minimum elements” under the induced partial order.