<p>For question #1: If there is a complete problem for uniform TC<span class="math-container">$^0$</span> under uniform AC<span class="math-container">$^0$</span> m-reductions, then the counting hierarchy collapses.  I don't know if this qualifies as &quot;bad&quot;.</p>
<p>For question #2: I don't know of a more restrictive type of reduction, for which there are complete problems for TC<span class="math-container">$^0$</span>.</p>
<p>For question #3: MAJORITY and division are both complete for TC<span class="math-container">$^0$</span> under AC<span class="math-container">$^0$</span>-Turing reductions.  If they were <span class="math-container">$AC^0$</span>-m reducible to each other, then this would give division circuits of &quot;MAJORITY depth 1&quot; (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<span class="math-container">$^0$</span> under AC<span class="math-container">$^0$</span>-Turing reductions, where an AC<span class="math-container">$^0$</span>-m-reduction to MAJORITY would collapse the TC<span class="math-container">$^0$</span> hierarchy (such a the k-fold composition of MAJORITY).</p>

CC BY-SA 4.0
2023-10-21T11:59:59.690Z
2023-10-21T11:59:59.690Z
Eric Allender
<p>AFAIU, we don't know any problem 
which is complete for $\mathsf{TC^0}$ w.r.t. 
<em>many-one</em> $\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.</p>

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

<blockquote>
  <ol>
  <li><p>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$?</p></li>
  <li><p>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?</p></li>
  <li><p>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?</p></li>
  </ol>
</blockquote>

CC BY-SA 3.0
2013-06-13T00:18:01.170Z
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
<cc.complexity-theory><circuit-complexity><reductions><bounded-depth>
$\mathsf{TC^0}$-completeness and reductions
Kaveh
# $\mathsf{TC^0}$-completeness and reductions

(Asked by: username_0 on 2013-06-12)

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?

**Tags:** cc.complexity-theory, circuit-complexity, reductions, bounded-depth

> **Comments:**
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2023-10-21. Score: 6 | Accepted answer

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).


---

