11
$\begingroup$

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?

$\endgroup$
1
  • $\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
    Commented Jun 13, 2013 at 0:18

1 Answer 1

6
$\begingroup$

For question #1: If there is a complete problem for uniform TC$^0$ under uniform AC$^0$ m-reductions, then the counting hierarchy collapses. I don't know if this qualifies as "bad".

For question #2: I don't know of a more restrictive type of reduction, for which there are complete problems for TC$^0$.

For question #3: MAJORITY and division are both complete for TC$^0$ under AC$^0$-Turing reductions. If they were $AC^0$-m reducible to each other, then this would give division circuits of "MAJORITY depth 1" (i.e., each path from input to output encounters at most one MAJORITY gate). Such circuits might, in fact, exist, but -- at least in the DLOGTIME-uniform setting -- we are far from having such circuits. One can also construct artificial languages that are hard for TC$^0$ under AC$^0$-Turing reductions, where an AC$^0$-m-reduction to MAJORITY would collapse the TC$^0$ hierarchy (such a the k-fold composition of MAJORITY).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.