真值表可化歸性(truth-table reducibility) m化歸的一種推廣.直觀地，對任意自然數集A和B,A可真值表化歸到B記為A鎮 B
簡介
真值表可化歸性(truth-table reducibility) m化歸的一種推廣.直觀地，對任意自然數集A和B,A可真值表化歸到B記為A鎮 B，是指對任意x，可能行地求解一系列問題“y, E By , +y2 E B} ，一"y。 E B} y}，若這些回答在一個(可由二能行計算出的)真值表中對應真值，則xEA，否則x貧A.而m化歸只能提一個問題，且真值表中，真只對應真，假只對應假.形式地，對自然數集A,B，若存在遞歸函式f，使得對所有二，xEA，若且唯若B滿足tt條件f(二)，則稱A可真值表化歸到B，記為A}t,B(參見“真值表條件”).真值表可化歸性也可等價定義為:對自然數集A,B，若存在遞歸函式.f}g，使得二EA，若且唯若對某個yEDK(二，,B卜f (x) =D,，則稱A可真值表化歸到B.其中D二表示典則下標為二的有窮集.若A< B &. B} A，則稱A與B tt等價，記為
A= B.
真值表化歸弱於m化歸與btt化歸，但強於wtt化歸與T化歸.對tt化歸而言，所有遞歸集之間都可互相化歸，且對一切自然數集.9 , A鎮 A. tt化歸是波蘭一美國數理邏輯學家波斯特((Post,E. L.)於1944年引人的.
A= B.
真值表化歸弱於m化歸與btt化歸，但強於wtt化歸與T化歸.對tt化歸而言，所有遞歸集之間都可互相化歸，且對一切自然數集.9 , A鎮 A. tt化歸是波蘭一美國數理邏輯學家波斯特((Post,E. L.)於1944年引人的.
