# $\mathsf{TC^0}$-completeness and reductions

AFAIU, we don't know any problem which is complete for $\mathsf{TC^0}$ w.r.t. many-one $\mathsf{AC^0}$ reductions ($\leq^\mathsf{AC^0}_m$). On the other hand, proving that they don't exist would separate $\mathsf{TC^0}$ from $\mathsf{NC^1}$, i.e. we also don't know they don't exist.

I have seen a conjecture stating that it is unlikely for $\mathsf{TC^0}$ to have any complete problem w.r.t. $\leq^\mathsf{AC^0}_m$ reductions.

1. What is the intuition/evidence/argument behind this conjecture? For example, are there results that say "bad" things would happen if $\mathsf{TC^0}$ had complete problems w.r.t. $\leq^\mathsf{AC^0}_m$?

2. Do we need the full power of Turing/oracle reductions for the completeness of the problems like majority? In other words, do we know any problem which is complete for $\mathsf{TC^0}$ w.r.t. a weaker type of $\mathsf{AC^0}$ reductions?

3. Do all known $\mathsf{TC^0}$-complete problems belong to the same equivalence class of $\equiv^\mathsf{AC^0}_m$? Or are there $\mathsf{TC^0}$-complete problems which are not known to be $\leq^\mathsf{AC^0}_m$ reducible to each other?

• I have seen the conjecture in secondary sources. If you know an original reference for the conjecture please let me know or edit the post to add the reference. – Kaveh Jun 13 '13 at 0:18