UP、β_n和FewP完全问题的相对同构性

RELATIVIZED POLYNOMIAL ISOMORPHISM OF COMPLETE SETS FOR UP,β_n. AND FewP

本文引进相对的多项式化归和相对多一多项式同构等概念，对ＵＰ、βｎ的ＦｅｗＰ的相对完全集讨论它们的相对同构问题。并得到如下结果：１（１）对任何ｍＰ，Ｂｎ─βｎＢｎ完全集Ｃ，Ｃ≈ＰＢｎＡｎ←→Ｃ为ＰＢｎ柱。（２）对任何ｍＰ，Ｂ─ＦｅｗＰＢ完全集Ｃ，Ｃ≈ＰＢ∪ｎ∈ＮＡｎ←→Ｃ为ＰＢ柱，其中Ｂ＝ＳＡＴ－∪ｎ∈ＮＡｎ。（３）对任意ＯｒａｃｌｅＣ和任何ｍＰ，Ｃ－ＮＰＣ完全集Ａ，Ａ≈ＰＣＳＡＴ←→Ａ为ＰＣ柱。２（１）存在Ａ使得≤ｍＰ，Ａ—ＵＰＡ完全集非ＰＡ同构。（２）存在Ａ使得ｍＰ，Ａ－βｎＡ完全集非ＰＡ同构。（３）存在Ａ使得ｍＰ，Ａ—ＦｅｗＰＡ完全集非ＰＡ同构。

In this paper, we first introduce the concepts of the relativized polynomial reduction and the relativized many-one polynomial isomorphism, then discuss the relativized polynomial isomorphism of complete sets for UP,βn and FewP. Finally we obtain the following results:1. (1) A mP,Bn-βnBn-complete set C is pBn-isomorphic to An if and only if it is a pBn-cylinder.(2) A mP,B-FewPB-complete set C is pB-isomorphic to ∪ n∈N An if and only if it is a pB-cylinder, where B=SAT-∪ n∈N An.(3) For any Oracle C a mP,C-NPc-complete set A is pc-isomorphic to SAT if and only if it is a pc-cylinder.2. (1) There is an Oracle A for which there are mP,A-complete set for UPA that are not pA-isomorphic.(2) There is an Oracle A for which there are mP,A-complete set for βAn that are not pA-isomorphic.(3) There is an Oracle A for which there are mP,A-complete set for FewPA that are not pA-isomorphic.