一致測度

一致測度

一致測度(conform measure)反映計算複雜J吐質的一種測度.設中為複雜性測度,若以任何遞歸函式為界函式的複雜性函式類所對應的下標集都是1一等價的,即對任何遞歸函式t tz,均有

{二}So.E(tl)三i {xSo E }tz,

則稱中為一致測度.並非任何複雜性測度都是一致測度,但是具有有窮不變性的測度則都是一致的,反之不然.此外,已知中的所有複雜性類都是r。的,並不能保證中一定是一致的.尚不知道中的一致性能否推得中的任何複雜性類都是:。的.

基本介紹

  • 中文名:一致測度
  • 外文名:conform measure

相關詞條

熱門詞條

聯絡我們