ON QUASI-LINEAR-TIME COMPLEXITY THEORY

This paper furthers the study of quasilinear-time complexity initiated by Schnorr and Gurevich and Shelah. We show that the fundamental prop erties of the polynomial-time hierarchy carry over to the quasilinear- time hierarchy. Whereas all previously known versions of the Valiant-V azirani reduction from NP to parity run in quadratic time, we give a n ew construction using error-correcting codes that runs in quasilinear time. We show, however, that the important equivalence between search problems and decision problems in polynomial time is unlikely to carry over: if search reduces to decision for SAT in quasilinear time, then all of NP is contained in quasipolynomial time. Other connections are made to work by Steams and Hunt on ''power indices'' of NP languages, and to work on bounded-query Turing reductions and helping by robust oracle machines.