一致測度

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

相關詞條

熱門詞條

聯絡我們