複雜性類的遞歸可枚舉性

複雜性類的遞歸可枚舉性(recursive enumer-ability of complexity class)反映複雜性類的能行性的一個性質.設中(f)為一個複雜性類，若存在一個遞歸函式g，使}<f)一{S}A}=} I i E叫，則稱}<f)為遞歸可枚舉的.若}<f)為語言複雜性類，則其re性即指其在能行編碼之下的re性.並非任何複雜性類都是re的，劉易斯(<Lewis , F. D.)於1971年首先證明了存在非re的複雜性類，哈特曼尼斯(Hartman-s , J.)於1973年進一步證明了每個布魯姆測度中都有一個子測度少，使得少有非r。的複雜性類.對於非r。的複雜性類，無法有一個能行的方法列舉出其全體元素.這是一種病態性質.但是，若複雜性測度中是有窮不變的，則關於中的任何複雜性類都是r。的(參見“有窮不變性測度”).