The isomorphism conjecture for constant depth reductions

作者：

Highlights：

•

摘要

For any class C closed under TC0 reductions, and for any measure u of uniformity containing Dlogtime, it is shown that all sets complete for C under u-uniform AC0 reductions are isomorphic under u-uniform AC0-computable isomorphisms.

论文关键词：Isomorphism,Constant depth circuits,Complete sets

论文评审过程：Received 5 October 2009, Revised 6 March 2010, Accepted 7 June 2010, Available online 11 June 2010.

论文官网地址：https://doi.org/10.1016/j.jcss.2010.06.003