一致測度(conform measure)反映計算複雜J吐質的一種測度.設中為複雜性測度,若以任何遞歸函式為界函式的複雜性函式類所對應的下標集都是1一等價的,即對任何遞歸函式t tz,均有
{二}So.E(tl)三i {xSo E }tz,
則稱中為一致測度.並非任何複雜性測度都是一致測度,但是具有有窮不變性的測度則都是一致的,反之不然.此外,已知中的所有複雜性類都是r。的,並不能保證中一定是一致的.尚不知道中的一致性能否推得中的任何複雜性類都是:。的.
基本介紹
- 中文名:一致測度
- 外文名:conform measure