Bounded Truth Table Reductions of P
Jin‐Yi Cai, Ashish V. Naik, D. Sivakumar · 1995
If there is a sparse set hard for P under bounded truth table reductions computable in LOGSPACE or NC 2 , then P = NC 2 . We give the details of the proof to this theorem. 1 Introduction Recently a 1978 conjecture by Hartmanis [Har78] was resolved [CS95a], following a breakthrough by [Ogi95]. It was shown that there is no sparse set that is hard for P under logspace many-one reductions, unless P = LOGSPACE. Bounded truth table reductions are a natural extension of many-one reductions and it is natural to ask what consequences can be drawn assuming there is a sparse set hard for P under bounded truth table reductions computable in LOGSPACE. In this note we give the details of the proof of the theorem that if such a sparse set exists, then a very unlikely consequence follows, namely P = NC 2 . This theorem is even valid for bounded truth table reductions computable in NC 2 . The proof for the case of 1-truth table reductions, which already generalizes the manyone reductions, has...