命名定理

命名定理(naming theorem)亦稱純正性定理.反映複雜性類基本性質的一個重要定理.是麥克萊特(Mccreight , E. M.)和邁耶(Meyer, A.)於1969年證明的定理：設印，為一個布魯姆空間。

基本介紹

• 中文名：命名定理
• 外文名：naming theorem
• 別名：純正性定理

命名定理(naming theorem)亦稱純正性定理.反映複雜性類基本性質的一個重要定理.是麥克萊特(Mccreight , E. M.)和邁耶(Meyer, A.)於1969年證明的定理:設印,)為一個布魯姆空間，則存在一個遞歸函式g滿足下列條件:

1. }}pR};>:iE}}為一個度量集.

2. bi Cp;)為一元遞歸函式，則汽()也是一元遞歸函式，且}(}p;>=}(}pa}rO.

上述結果表明，任何複雜性類}(y)都可以在某個確定的度量集中找到某名(即}PRC,>>.這便是命名定理名稱的由來.此外，由於度量集總是某個h純正函式類的子集，所以，上述結論可以推得:存在一個函式h，使任何複雜性類都可由某個h純正函式命名，純正性定理之名稱因此而得.