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?

  • $\begingroup$ 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. $\endgroup$ – Kaveh Jun 13 '13 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.