[32] We say that A is truth-table reducible to B if there are functions g1,...,gm and a Boolean function f where yi is true iff gi

(a) ∈

B, and f(y1,...,ym) is true iff a ∈ A. We consider only polynomial-time truth-table reductions where f and the gi’s are computable in polynomial time. It is clear that if A many-to-one reduces to B, then A also truth-table reduces to B; and if A truth-table reduces to B, then A also Turing reduces to B. Use time-space-bounded Kolmogorov complexity to construct a set D that is complete for E under polynomial Turing reduction but not complete for E under polynomial truth-table reduction.

Comments. Source: [O. Watanabe, Theoret. Comput. Sci., 54(1987), 249–265]. Improved in [B. Fu, SIAM J. Comput., 24:5(1995), 1082–1090].