Autoreducibility and mitoticity of logspace-complete sets for NP and other classes

摘要

AbstractWe study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:•For NP and all other classes of the PH: each≤mlog-complete set is≤Tlog-autoreducible.•For P,Δkp, NEXP: each≤mlog-complete set is a disjoint union of two≤2-ttlog-complete sets.•For PSPACE: each≤dttp-complete set is a disjoint union of two≤dttp-complete sets.