複雜性測度的平行性(parallelity of complexitymeas ure)計算複雜性測度的一種性質。
基本介紹
- 中文名：複雜性測度的平行性
- 外文名：parallelity of complexitymeas ure
.設印,})為布魯姆空間，如果存在二元遞歸函式h，使得對任何i，7
複雜性測度的平行性
對任何輸人x，可以能行地從此兩個算法中挑選出複雜性較低的那個進行計算.而且這樣做並不增加整個計算的複雜性.確定型圖靈機的空間複雜性測度和確定型多帶圖靈機的時間複雜性測度都是平行的.但確定型(單帶)圖靈機的時間複雜性測度恰是非平行的.
