析取化歸

析取化歸(disjunctive reducibility)亦稱d化歸.m化歸的一種推廣.形式地,對自然數集A,B,若存在遞歸函式f,使得對所有.x,xEA"-}Df<二。自B並必,則稱A可d化歸到B,記為A鎮dB (D,是典則下標為y的有窮集).直觀地,A落,,B,是指對仟何二,可能行找到有窮個自然數y1,yZ,...,yR,使得二EA,若且唯若這些元有一個在B中.即B滿足析取式“y,EBVy}EBVwVyEB".由於對任何自然數集A,B,A毛}B t->兀鎮刃.因此,由d化歸導出的結構與。化歸導出的度結構是同構的.d化歸比m化歸弱,但比tt化歸強.

相關詞條

熱門詞條

聯絡我們