複雜性測度的合適性

複雜性測度的合適性(properness of complexi-y measure)計算複雜性測度的一種性質.設中-}};};E},為一個布魯姆測度.如果`di E c}(}為遞歸函式~};E}(}})).即只要複雜性函式中，本身是遞歸的，那么計算它自己的複雜性將不會超過中本身.則稱中為合適的.直觀上，若中為合適的，則為了確定一個算法M;的複雜性中，這個過程的複雜性將不會超過執行這個算法從所需的複雜性電.因此，合適性是對複雜性測度的一種自然要求.但是，並非每個復性測度都具有合適性.此外，並行性與合適勝是相互獨立的.