受界合取化歸

受界合取化歸(bounded conjunctive reducibili-ty)亦稱be化歸.一種可化歸性。

受界合取化歸(bounded conjunctive reducibili-ty)亦稱be化歸.一種可化歸性.是用類似btt化歸對tt化歸的限制辦法,對合取化歸限制後得到的.形式地,A可b。化歸到B(記為A鎮bcB,是指存在遞歸函式f和常數n(稱為該化歸的範數),使得:d x)CCx E AHDf(二)c B] }「I Dt(二){v n]]"直觀上,A可b。化歸到B,是指存在一個常數n,得對任何x,可找到不超過n個自然數yl,yz,...,y,},使得xEA,若且唯若合取式“y1任B八,yzEB八,…,八ymEB”成立.
用類似限制提問個數小於某個常數的方法,對d化歸與p化歸進行限制後,即可得到受界析取化歸(即bd化歸)與受界正化歸(by化歸)的概念.

相關詞條

熱門詞條

聯絡我們