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.